1000
-8347220 -7643722 -7275472 -7179125 -6842918 -6333566 -5695018 -5013986 -4768049 -4028250 -3641095 -3512595 -3416805 -3122786 -2878062 -2306628 -2210851 -1840717 -982940 -358823 -59521 -131398 -15169026 -14941685 -14479250 -14497529 -13863252 -13800236 -13174678 -13073201 -12455548 -12303613 -12095547 -11560848 -11417612 -11324013 -10787818 -10080979 -9440582 -9382005 -9193986 -8769199 -8808484 -8608386 -24747910 -24252242 -23392647 -22521712 -21823577 -21697457 -21068666 -20720148 -20525270 -20101121 -19419969 -18665733 -18216109 -17411016 -17098854 -16904644 -16017797 -15989953 -15850859 -15649159 -15116023 -15108699 -35692001 -35032658 -34412968 -33669454 -32876284 -32748954 -32152065 -31933192 -31582502 -31257774 -30757014 -30176732 -29520501 -29415703 -28522069 -28083597 -27640111 -27584337 -26822877 -25928017 -25729040 -25646285 -45778799 -45130558 -45097023 -44368342 -43900300 -43047036 -42851292 -42115663 -41539220 -40917191 -40108529 -39664498 -38800829 -38320168 -38380365 -38307333 -37904946 -37410143 -36913269 -36736257 -36059408 -36061727 -53842815 -53257035 -52818304 -52462640 -51686012 -51477962 -51013713 -50301691 -50369429 -50284442 -49413516 -49369831 -48841570 -48609032 -48147683 -47763004 -47001968 -46658902 -46666299 -46525940 -46340222 -46230136 -64346030 -63627324 -62788839 -62478984 -62010814 -61349937 -61223010 -61031062 -60141648 -59319201 -58566989 -57915968 -57715549 -57157468 -56753853 -56535121 -55791318 -55535526 -55339642 -55401412 -54962906 -54075571 -72371386 -72013870 -71285896 -71169758 -70585045 -70337068 -70187863 -69292525 -69035053 -68927574 -68376275 -67753913 -66983901 -67060475 -66812336 -66147020 -66117238 -65878945 -65370330 -64665895 -64393788 -64326657 -81934751 -81629369 -81034861 -81036452 -80218352 -79363680 -79041887 -78265902 -78105455 -77570375 -77562830 -77635354 -77005080 -76727935 -76346129 -75492660 -75227677 -74728784 -73920693 -73317310 -73115108 -72469493 -89718435 -88866749 -88678564 -88678284 -88740604 -88171752 -87471963 -87510646 -87472711 -87059821 -86439702 -86286606 -85670884 -85407903 -85492941 -85211425 -84913638 -84130248 -83591536 -82724147 -82361749 -82249956 -98524612 -98023434 -98091111 -97669041 -96861706 -96197635 -95580236 -95475647 -95360507 -95228434 -94707534 -94214665 -93767257 -93221071 -92761418 -92344160 -92150171 -91392453 -91080399 -90816649 -90904362 -90030707 -107633085 -107579116 -107131624 -106794144 -106288665 -105851350 -105014742 -104998113 -104796014 -104646105 -104447856 -104408082 -104304738 -103470353 -102776312 -102245255 -101624716 -101693384 -101328539 -100479685 -100166328 -99358785 -116516385 -115812866 -115007337 -114294964 -113938033 -113203023 -113282657 -113215988 -113298623 -113045983 -112915947 -112555358 -111961297 -111535884 -110767847 -110096774 -109520801 -109456742 -109093931 -109013879 -108805022 -108118896 -124975869 -124192929 -123602396 -123646771 -123349764 -122831039 -122663475 -122445803 -121804066 -121744077 -121168886 -121001962 -120571070 -119912424 -119202344 -118335561 -118013814 -117769185 -117786877 -117518993 -117195352 -116830972 -133156131 -132841312 -132863475 -132140574 -131280824 -130470889 -130033346 -129909730 -129200370 -129237301 -128511981 -128479889 -128298650 -127758818 -127548759 -127489221 -127370672 -127312260 -126721241 -126363275 -125479589 -125473825 -143106639 -143187578 -142382654 -142131475 -141678925 -140808485 -140106964 -139772164 -139868563 -139199658 -138601193 -138205801 -138194637 -137873962 -137656004 -136893981 -136561946 -135695481 -135264541 -134432878 -134132687 -133448801 -151498799 -151150874 -150312252 -149660376 -149717224 -149231019 -148665100 -148185493 -147549888 -147005970 -146843859 -145962771 -145207173 -144599026 -144429371 -144511087 -144410490 -143863651 -143903071 -143735739 -143710613 -143135471 -160096463 -159285827 -159019004 -158722816 -158089461 -157428217 -156529676 -156552595 -155941225 -155636103 -155208194 -155265625 -154666712 -154029201 -153541224 -153028722 -153064872 -152892337 -152707900 -152567408 -151764080 -151830323 -169069792 -168366747 -167467760 -167417214 -167463486 -166792163 -166388492 -166427213 -165754698 -165767400 -165757712 -165161734 -164296278 -164205587 -163729322 -163220684 -163317033 -162611261 -162378488 -162118067 -161646716 -160973238 -177064152 -176993544 -176846019 -176039160 -175974715 -175858859 -175680683 -175044535 -175117251 -175143030 -175033588 -174334013 -173710372 -173631636 -173147947 -172252845 -171939654 -171223136 -171285138 -170450014 -170209348 -169869036 -184492419 -184425282 -184242671 -184272609 -183794285 -183074581 -182948680 -182284608 -181986985 -181676833 -181593935 -180971080 -180726283 -180358994 -180031860 -179233566 -178926559 -178977607 -178616346 -178128474 -177791649 -177569745 -197208360 -197000249 -196190498 -195645979 -195299201 -194937294 -194278310 -193743607 -193121195 -192532849 -192053657 -191533954 -190818079 -189918864 -189373708 -188912609 -188233032 -187574348 -187314503 -186684210 -186123847 -185344441 -204667508 -204501971 -203635872 -203501841 -203032101 -202973214 -202748107 -202006759 -201213776 -200444620 -200437796 -199965656 -199113309 -198680506 -197920304 -197132475 0 462015 381923 578958 1207316 1573801 1577825 2433730 3271023 3435107 4117314 4713403 4640388 4995812 5709714 6309483 7082940 7441049 7569875 7875065 8214641 8722083 8648444 8697536 9074996 9797079 10123063 10654288 10652874 11056256 11200610 11248364 11622763 12077209 12252240 12722827 13620610 14311443 15076356 15582998 15588079 15912340 15875451 16558447 17178183 17671797 18347618 19204199 19709138 19748931 19724252 19702727 20148172 20636991 21487038 21454024 21403172 21742493 21949394 22535323 23194176 23669000 24546839 25386209 25730806 26009884 26655038 27225075 27539028 27659242 28169966 28324187 28924633 28938360 29799489 30244504 30548600 31031165 31841347 32363357 33083547 33095656 33000057 32983762 33597341 34371225 34672279 34735248 35246158 36027429 36791176 37324265 38003955 38211223 38641387 39255454 39519043 39469481 40048719 40812774 41362730 41868046 41970045 42360621 43109321 43029867 43720814 43742034 43880244 44310041 44943761 45197160 45643442 46124324 46551686 46944694 47368385 47292495 47470885 48273910 48785230 49137229 49355703 50057369 50599296 50630792 50943738 51065664 51190766 51861086 52321825 52802883 53113059 53100510 53767889 54509230 54534049 54850319 55103654 55270912 55967132 56213802 56800428 57153194 57476409 57512217 58337636 58333331 59007126 59503168 60304903 60242713 60313669 61145908 61227774 61141578 61704200 62470206 63277351 63909992 64096791 64708698 65279828 65597803 66056352 66468603 66443916 66887870 66797377 66943108 67231943 67509631 67516046 68175438 68749172 69292098 70123856 70040040 70267254 70874574 71167554 71218640 71994337 72019933 72433941 73157502 73410817 73975008 74580846 75356635 75655188 75939385 76475107 77003714 77715915 78511807 78507137 78624773 79352588 79540668 79806536 79711273 80337010 80833906 81219053 81410280 82188555 82631889 82724694 83500782 83803608 84622850 85516833 85635164 86311888 87134367 87539037 87733512 88234525 88353272 88762382 88740474 88875100 89707918 89973868 89890415 90191840 90381402 91225891 91563225 92453168 92887816 93463638 94230558 94300677 95099253 95735317 95849300 96013836 96566452 97284649 97784970 98283177 98250254 98977680 99488578 100313074 101102589 101303417 101235120 101827504 102089904 102024328 102275581 103167457 103649097 104277524 104319685 104940472 105577314 105840171 106440859 106670298 107543874 108181195 108502979 109215522 109640812 109876202 110439479 110361310 110758289 111100655 111067810 111910479 112262936 112243638 112520295 112988523 113440603 113429390 114315097 114228637 114367403 115254781 115733891 116105155 116894859 117032251 117532451 118068592 118568882 119169268 119118888 119086824 119762378 120370887 120692984 121112359 121851187 122159688 122135211 122887834 123745793 124421697 124837584 124843939 124826680 124960428 125222374 125183192 126072022 126545978 127354851 127680068 128467785 128473551 128500848 128781220 129551412 129529795 129797291 130422379 131122030 131586082 131821667 132504126 132680514 132908332 133270751 133841272 134494960 134634773 135508823 135873062 136465961 136950021 136905144 136891915 136860886 137753432 138393507 138916892 138865425 138839006 139484909 139539140 139504041 140110748 140890529 141693922 142156195 142658186 143334778 143635014 144264883 144725586 144741289 144685175 144586951 144978646 145398164 146173935 146777275 147534825 148256723 148426972 148554917 148868245 149041589 149495585 149818955 150327316 150524409 151350482 152250471 152219095 152724054 152942460 153139114 153146434 153728563 153730970 154451445 154930412 154994990 155296608 156179489 156540451 156877337 157178996 157786360 158591718 159029688 159187759 159847673 160391337 161018692 160989600 160946264 160875669 160994539 161399305 161419451 162296965 162660238 163395168 163697790 163954953 164481600 164750734 165115054 165607205 165603660 165927090 166189200 166802897 167402862 168216286 168785819 169655866 169958872 170609112 171488889 171853567 172706862 172902937 172837706 173555125 174254090 174919505 175786976 175922467 176237945 177135073 177404164 177918535 178777660 179347488 179674864 179738064 179880009 180400536 181236115 182034849 182198215 182798213 183351567 183767379 184322708 184444699 184562045 184479090 185374465 185972543 186222567 187031166 187865683 188364876 188444556 188947883 189314883 189337103 189368351 190261794 191099840 191219916 192007304 192387517 193213095 193601718 194107745 194615438 194751569 194978874 195372473 195972632 196421125 196376501 197267093 197468628 198053633 197956664 198654377 199441069 200276149 200611083 200888930 201506307 202318151 202410534 203069407 203413036 203507984 203480825 203553779 203785326 204388829 204328358 204593125
550495244
7000
925 1000000000
59 1000000000
386 8102781
975 204951391
536 387133571
473 48383707
648 205942528
921 560351658
913 382300083
54 13277410
108 1000000000
649 102932675
56 24850507
753 211820980
822 164915936
399 29106100
894 114601782
418 312089051
303 503906813
355 391983908
426 1000000000
777 1000000000
718 139542697
614 492996938
956 144982377
847 328462342
228 109579873
70 23736671
821 114130260
147 140605415
935 518092242
925 83846005
603 481958634
781 20142677
561 204896276
907 275887279
256 87887035
422 1000000000
441 23085148
278 492670185
971 3530007
756 44845560
79 40227715
728 751385669
901 503377284
657 12247326
44 110724453
224 151882036
716 43401213
189 137148193
502 294052765
463 1000000000
770 278558698
534 1000000000
63 53182239
691 952081013
974 463636841
326 51052537
623 213179277
614 91274307
249 32692503
148 96602691
540 74867588
863 95439987
17 374402849
656 2595324
184 669269647
94 11722465
688 60368987
826 1000000000
82 624818707
364 26281007
885 129017947
851 33179823
42 230571165
832 11630228
665 133897725
410 164538933
41 347736265
642 1000000000
658 194228224
799 5919329
45 318696025
890 42876006
738 387013619
403 1000000000
584 270665235
401 44163078
88 245867233
36 14251840
50 1000000000
854 482139407
357 15483400
196 509435658
393 153637018
569 75902733
311 273471195
290 55937177
591 200523581
50 192442771
960 1000000000
663 191845608
803 74287011
754 324640291
783 597652545
170 176436247
725 318224025
935 325310751
149 127820149
611 1622598
878 55046386
963 221710800
568 586673772
386 585110267
773 129376086
182 395839106
866 11697418
423 1000000000
762 155584487
918 41012173
714 78017280
827 66676172
349 218177265
781 1000000000
193 422931971
549 18319555
126 1000000000
490 35734033
677 328444780
109 51700920
414 212360975
430 247144485
648 11331755
700 78180467
652 83890518
671 1000000000
929 127171233
256 138304388
656 196559440
111 105694525
793 77201750
859 104276093
771 40214599
661 68143430
599 248492317
92 334254520
956 360270480
113 153134005
322 3606067
68 1000000000
275 237451104
236 58950589
773 523126032
74 45264179
592 316156102
29 28491370
45 89934259
517 108204568
155 712967891
348 360173784
236 184433231
120 8520094
837 218962880
953 44448628
560 147084903
504 163371362
69 42791173
93 195853645
68 122941384
247 30728786
11 58182245
551 92813798
389 3866048
180 240702424
192 221899096
831 1000000000
189 7688995
999 753430420
107 404248799
365 42434770
514 124454022
160 45012668
820 141057139
490 181511431
159 189253725
432 54257121
603 1000000000
68 505376541
505 65592272
134 413398280
961 264370141
597 371065548
626 442854141
362 374353717
284 1000000000
925 109100762
17 120202909
853 141705331
798 1259466
146 101400098
350 120118849
341 1000000000
847 16645631
110 1000000000
177 768508754
364 933276603
157 26848843
888 621833417
979 118065028
714 2871837
50 95819155
921 579759361
411 661068080
21 200212754
101 694549186
607 293100046
353 647721659
623 192641266
702 215193091
612 113760141
29 644343529
975 123273780
638 524281233
599 63795677
96 88159482
149 238593645
563 157882989
896 196855876
745 832857000
497 825430645
487 186458772
792 1000000000
952 419238479
508 1000000000
442 3926802
622 237391930
885 690712341
133 149857600
426 385143805
42 265579601
489 92815871
812 146474114
545 1000000000
36 48566458
763 138348617
706 276665830
342 187109071
189 410290380
675 199516232
685 356392547
57 428714338
36 174515891
897 327007388
663 138876075
371 13333703
929 8199100
62 297305789
143 92379306
859 181383451
388 110222393
657 312362431
46 23874665
257 240737114
926 111595026
882 218893103
275 190549807
757 136317715
189 611648
313 1907997
238 78815565
519 118582573
899 323346291
927 455874618
327 359839996
784 57706371
520 1000000000
771 615641254
110 69207901
287 308392745
434 145852070
5 388061422
644 642877035
172 74029954
691 398350716
301 143338212
144 267919464
696 1000000000
194 574696265
812 193648895
826 207460926
338 8593414
560 40117566
121 329157013
283 72755945
386 52526658
227 18834538
388 583447641
201 150973701
360 471342632
877 1000000000
901 387177058
710 259774458
628 99643282
365 57593608
197 16322512
505 67443051
807 528736985
787 565277872
859 1000000000
339 134365919
552 98678604
984 36414654
567 8370581
139 58297021
327 42319873
563 72057238
801 24654342
344 512135819
261 98762394
804 576021115
474 845972326
981 485426258
17 126308495
979 1000000000
177 501320061
295 39166021
851 7199452
641 104699926
78 1000000000
912 140794414
211 464063589
989 44293098
97 55775641
343 142539081
306 109516361
927 53067996
619 106378038
180 686465834
470 72626289
687 1000000000
195 348842002
679 366188736
1 759590345
902 137663638
361 94836566
617 4937222
595 832238518
450 406303342
910 158969254
369 61945902
138 220751006
245 41096489
640 186491405
415 364228823
216 149976166
15 155681140
601 867505963
796 389576556
972 1000000000
774 630341412
720 6172719
542 876211405
422 31189329
420 1228721
502 431713433
119 395143828
967 56852125
1000 316050478
977 420039721
975 5342266
789 1000000000
227 201462962
731 2434058
876 1000000000
146 76934910
291 143088960
715 2262441
304 1000000000
718 84808101
330 1000000000
2 289090507
242 88633472
887 59895758
967 1000000000
686 39396467
890 1000000000
959 1778904
482 1000000000
545 79287016
912 299703029
613 85957001
516 179713334
202 191305232
693 58208860
753 99060455
676 212712614
154 1000000000
640 54054693
12 423578891
986 18907962
687 727162087
641 468185
796 100223437
86 1000000000
771 115845
617 331261765
811 156038205
713 99714607
117 1000000000
254 208959523
889 242207566
2 131371313
630 233656153
586 3201639
20 96364632
641 0
36 180462169
365 63060885
718 1000000000
542 25804321
425 233592524
957 647531854
430 142881953
490 310214967
12 158808869
660 80038344
452 1000000000
11 393695338
526 209489355
449 151711301
993 42053282
611 99082308
653 927040632
924 268048581
876 2703859
154 23457541
603 1000000000
605 340437629
837 363245617
230 433220658
279 456023291
693 14524863
428 467069626
545 887558521
354 1000000000
3 309374499
321 175027071
506 1000000000
170 280476915
671 647603221
181 279115757
874 74091623
857 148724040
10 81042141
31 551295300
719 51984163
550 50212997
754 48106670
687 197194521
11 11377947
58 122866163
417 177533616
166 32882536
141 337852528
452 529142437
342 120730826
411 299766167
837 122227352
803 5310054
842 95477477
678 239567133
980 63083393
114 256195935
636 1000000000
463 1000000000
233 614791146
326 931057852
364 855407655
630 6496742
164 4759786
313 75059771
570 12575752
532 688391275
157 311912498
801 1000000000
158 2952830
352 146560838
509 380357282
793 94175295
817 203982555
539 32713812
355 78890677
918 95294029
954 27850477
963 47178048
719 163352855
882 390768960
753 1000000000
10 378940153
161 151016127
76 8273310
798 399087113
551 843262714
298 1000000000
988 401372255
378 142554149
642 15263364
848 350456421
674 322600856
324 250936416
580 769907471
717 66160650
535 3588350
4 658497552
523 443267666
753 337990739
426 62823595
243 114876346
713 191056131
66 125557113
795 41918215
287 57166239
54 1000000000
50 36263969
986 176877572
954 412058116
208 33065583
560 97843842
1000 302564992
212 170045657
265 409756025
37 11935814
764 11864282
483 810776560
120 19636811
247 70791653
94 244875963
889 1000000000
389 7460574
352 156747968
758 78746549
101 178982607
209 1000000000
655 307579057
293 908215483
623 1000000000
154 272896679
156 312668352
858 617816
87 227399878
962 20306938
24 97618171
453 454741276
966 84654065
249 46547593
554 1000000000
582 199517653
595 21419401
469 494768987
266 90302624
6 249516173
646 620666452
576 100021231
776 97468098
588 219828503
376 40810098
689 10792646
237 915816666
232 48443640
383 1000000000
240 281258876
680 4395455
706 1000000000
605 41666645
646 274702785
193 685567188
795 67989975
962 311245817
378 1000000000
424 1000000000
282 79982908
764 1000000000
60 63103509
854 1000000000
111 1000000000
853 808205386
732 755062006
993 85446603
338 1872508
92 38011374
34 200684016
251 396080025
212 167779744
337 10957310
127 51204184
884 68950852
12 112479428
796 590632240
962 1000000000
794 190148199
570 34575779
430 6596602
227 474086731
191 43761999
670 234042492
630 29554895
115 7886724
106 828713193
161 224329481
380 421896142
305 709232498
356 89598402
682 101846005
713 339631609
477 426386627
139 729700535
201 126009909
547 1000000000
831 106103919
697 146871743
46 18177871
468 48992010
327 80044820
845 8119663
898 153109562
91 46155066
206 225835084
583 212350242
364 172393625
385 52638393
227 97656060
288 126998241
716 47314570
629 46847345
790 604200391
15 206118984
538 49939406
319 294172289
168 1000000000
268 189109387
687 1000000000
607 203416800
544 78561207
303 30639917
298 104570331
933 10594676
926 14303414
137 753358513
803 120474585
674 43914744
218 47306508
849 3516825
850 170656967
53 93054992
149 743729829
287 1000000000
56 137322404
270 255391023
613 421578297
259 451943466
748 101758450
109 330584864
292 770022850
974 53965401
190 610820158
851 60183826
402 186623056
190 409197025
71 75223152
887 130111207
749 17091120
69 69677586
581 101572646
145 573501474
191 422856806
387 94847926
954 284172332
490 79019195
239 1000000000
582 936664689
165 640655712
640 199192413
693 7643274
432 651550636
863 357295669
877 185446426
282 1000000000
56 11786432
470 27169527
449 51810145
284 21115876
111 379123513
28 652185809
994 1000000000
997 138408483
795 469031941
736 519020099
906 115416950
637 111199835
318 552014293
51 437335011
288 6663381
154 181806587
919 388221619
395 55832799
660 6368260
990 321236813
94 135732330
834 190390795
814 17757267
536 14667793
628 1000000000
375 91911214
439 21754772
424 185688107
592 7847547
171 6553715
134 149960001
279 61064103
10 27097813
44 1000000000
947 47007271
451 441644980
714 663571985
4 80424810
407 90271959
431 296833479
513 126583904
114 178267991
472 159612715
168 7270560
894 320316624
799 107566968
400 434309794
727 129165629
473 1000000000
609 2511532
559 43991668
165 260818850
714 1000000000
786 1000000000
27 116279061
385 150145774
498 203968064
65 194450991
838 1000000000
867 475583310
735 78855740
103 3351308
471 20266579
964 16305901
859 39279731
450 321079727
598 147960386
843 874731210
390 345782230
348 76601677
83 73684740
128 278971285
302 93375375
860 103240413
999 29001756
11 248097827
261 823429729
755 35050756
425 645276045
156 883804385
466 232247017
471 155697899
889 73264756
636 51339200
774 6836461
922 8893502
752 1000000000
378 55641343
151 1000000000
844 1000000000
908 786443202
270 59060743
983 1000000000
275 123181990
751 330963308
177 99147749
845 164360229
817 20330194
496 196133824
530 221718592
737 630442949
140 515777436
664 124116939
817 10213265
460 510425160
743 108775804
510 595993038
22 101868007
221 422932600
975 85699290
314 41919831
609 377410387
236 227365296
382 24400064
980 101913102
667 82630696
793 232882076
162 210598264
932 95977641
219 181060774
757 177264222
998 236288343
635 133942402
98 441500760
943 1000000000
23 160373540
200 125195463
742 56848997
975 25939192
503 1000000000
275 340274168
449 229915310
493 204974985
349 139634630
636 43583961
490 221283952
610 249282300
625 1000000000
668 215574014
697 1000000000
132 1000000000
371 637985310
10 764192602
263 1000000000
573 38852689
660 1000000000
302 393302968
778 149370114
709 93868274
459 234881570
249 175692908
908 190425710
66 268283566
240 36489734
193 617886567
109 2295285
230 244536307
787 14616215
912 1000000000
611 123729823
808 77933321
157 144160205
926 546966165
960 857548449
993 100307902
549 153145167
353 18556506
355 189960395
311 393803302
771 5873549
651 109387405
612 760925861
396 586464590
671 13882200
411 563256899
740 208321307
599 154475727
146 4385819
729 814442996
233 616042899
888 184333591
635 21858702
109 509926193
117 759152530
952 56834176
810 259397826
192 35553250
456 97956383
390 1000000000
135 668768443
545 813373694
824 43207626
858 400205937
259 425941855
288 11522782
831 788258793
276 413780394
309 575812036
918 292111913
100 946800844
261 160232672
117 1000000000
889 297373743
767 32130344
532 1000000000
179 451181051
323 96067636
945 1000000000
921 3657503
416 96884705
724 204823834
105 280619683
764 57628343
995 334406053
802 29829889
15 287008097
422 1000000000
188 492382995
895 842206052
243 57607746
653 10128796
779 188191886
146 219705033
765 184019261
443 388159521
193 4343388
131 103875763
62 1000000000
736 98460027
997 4361592
162 1000000000
469 1000000000
58 38549273
847 146784163
24 186933202
58 57907833
291 19250661
263 118154873
644 174577912
598 2858802
866 986159454
694 1000000000
702 123999133
576 262666049
320 78733682
427 60532428
631 91857975
288 148874459
11 51951497
190 42650175
661 25369092
510 118919219
397 498262768
239 455276707
930 10254547
906 495598427
773 48395383
759 448038943
717 998737491
261 8875720
371 799128028
429 283963688
895 104617167
62 34233829
848 1000000000
97 1000000000
407 243190706
309 95013976
499 393317426
587 423217596
661 97624470
123 692784511
612 350596854
244 1000000000
313 267963766
263 110727343
403 104178983
459 661670486
347 1000000000
177 64673444
905 270173524
144 221127850
124 1000000000
905 178828557
357 5715897
932 93662860
795 101019591
688 174793942
671 138872688
973 157343738
128 20198199
788 248355897
463 298241023
853 240425586
451 79783479
351 218266650
38 18598039
291 86641349
853 61244652
241 919846
266 286233918
784 573752985
165 137077551
848 1910943
837 8910607
906 57910697
355 181081294
70 54790248
215 1000000000
51 11964999
768 127368622
818 5249015
966 283424329
314 20144616
162 124272036
844 98299631
420 372409020
640 863157581
603 55484483
429 43147872
664 6488798
155 41659716
155 101966011
467 262040260
419 611931770
397 56855786
160 103909324
448 114040086
595 360726052
381 8068993
476 131622949
972 84326056
858 14460518
844 57586961
398 35540316
397 140732688
799 1000000000
776 467297711
582 1000000000
181 61496252
122 32523103
963 42308394
260 389051519
403 89937741
404 547475316
732 564261
625 719329619
207 37730415
156 50624437
932 244206597
716 75624202
570 232752506
402 36742545
457 872322216
693 192795209
275 22711643
974 125392028
749 163779973
493 716252049
442 1000000000
585 293177801
711 154400256
34 173649880
511 17218528
962 47037964
344 290994606
54 361422668
674 213738851
329 240841439
198 17028587
753 242015698
708 345817112
598 19164326
291 43106061
81 191924206
580 243768410
930 1678117
142 22871892
248 107538990
298 42323824
931 415382292
424 828248600
589 44851360
959 38879868
51 469296889
383 762563011
432 147536313
826 36123695
82 107222035
29 451584740
49 94105213
427 24217758
318 189389206
369 13426624
225 1000000000
586 934268052
857 413243927
324 58626223
127 158139326
399 179085836
586 5347786
516 163044182
123 190667808
451 362458051
434 1000000000
171 179073570
310 820163187
93 1000000000
591 233418294
697 294700123
982 971026936
525 99796147
675 322315813
532 197855334
557 44234091
124 69942509
149 30544131
710 14310533
458 387030080
537 46526235
205 207447411
381 109262000
782 762446927
116 31224583
772 55378289
932 9262880
248 43015113
981 73192122
625 15837233
640 150983021
192 155720513
324 2808481
100 59768381
451 1000000000
254 209846060
794 455554009
965 16647570
691 684598525
314 200004080
590 1000000000
277 138254575
339 638916989
981 63037666
225 81487699
715 510071132
464 66951107
14 69592595
161 19847998
111 2093076
932 653534001
813 89238974
96 1000000000
241 185260292
150 174633321
346 178160955
309 316252978
866 50113925
726 489563361
862 433404491
960 20460952
344 30310248
924 138970818
416 6085954
122 163694383
237 479435263
497 105698096
944 174433858
257 1000000000
121 31719975
60 87960784
647 12344843
607 72046921
890 170271590
541 464341647
811 30095068
836 643384358
946 36072907
980 160758171
94 241163314
174 1000000000
120 198881803
642 18616652
968 131586331
959 107135215
517 123763126
286 9095003
959 820038791
502 101515117
495 135750497
128 348212571
605 446021757
947 65020299
856 283799533
456 88328091
913 237933283
303 163818887
215 104680628
519 79083000
499 148067718
64 260089034
148 38767129
940 442991352
731 688891600
472 816920613
480 120260751
551 166873998
10 333553661
503 606854117
682 14815938
24 42053591
63 1000000000
763 34890207
626 230872977
184 1000000000
138 113175956
854 153410764
408 42574149
790 778199241
644 95719951
687 1000000000
197 8184971
634 206527313
931 70479110
206 1000000000
584 83471251
852 408657805
569 650123737
116 1000000000
633 186273011
845 244904849
678 916305216
40 162960430
424 289321787
236 82275655
464 180225642
890 523951278
126 283604823
281 320111642
593 49638277
786 172558339
329 496495034
308 253713359
592 341331364
176 530598673
995 74082811
878 215593260
581 19423542
141 176451385
316 215682935
510 125207617
672 1000000000
904 1000000000
482 70765548
468 71171342
474 947205801
289 1000000000
807 260876187
672 147696666
282 57226743
105 1000000000
650 187922113
891 159586074
616 146410489
631 38401994
892 28819344
444 47124563
653 579414783
931 70968652
971 113697092
195 58147155
543 95747735
549 1000000000
745 155305661
360 1000000000
904 433948956
789 1000000000
413 167190002
508 14515011
687 503485118
756 475208171
367 124892700
14 141766491
885 320766964
201 52823996
872 1000000000
670 94484600
145 222294098
284 76984326
839 135171692
788 40766865
843 170643235
910 174158613
412 5200793
305 278991892
923 348358456
478 12476542
23 207736406
804 16223407
417 757569652
340 61999649
521 39334674
45 1000000000
710 49352501
440 811073286
105 251501781
237 127656870
737 1000000000
523 673047151
671 233952127
818 434347378
514 1000000000
867 20436206
83 8945507
142 2178998
473 269955022
114 42681143
6 247568132
96 309893061
447 43758328
752 223138516
398 519875330
873 141014717
259 247809419
483 123930068
861 35770521
927 1000000000
237 366396991
301 175040752
843 183871170
908 32453156
150 166146869
405 537360951
974 134619653
799 5955316
740 53918110
355 190618235
856 71461241
697 13290815
609 208688879
984 408631280
104 511823709
728 529661237
301 1000000000
202 655273965
815 171010062
62 5080304
854 477171305
59 1000000000
299 10811614
202 57196178
390 49176360
979 422857404
470 194668187
493 584370754
804 82641169
32 23735190
47 361031206
333 78707783
80 15890847
60 199311917
798 355291485
988 380479631
410 258944359
926 100544009
876 496911845
937 307526619
667 186313784
542 43853984
288 63867581
549 26213680
554 1000000000
597 347002973
410 13715480
566 396257874
551 483894166
170 38456452
882 18487602
718 617168717
875 30966955
477 248499676
793 249526832
444 1000000000
692 50301563
822 199309256
958 63835022
881 561950646
180 36552117
261 113942548
377 96379523
43 686133605
483 688604962
35 1000000000
938 744875215
20 360232657
687 1000000000
687 1000000000
514 141533850
451 256760102
234 99363628
265 44070
719 54151931
929 423144077
971 450609442
642 312647479
731 57110408
500 256399275
794 9946813
737 28771192
766 116737893
702 121737790
479 285713330
790 298065412
590 29896086
686 73506285
779 1000000000
65 1000000000
101 252500141
317 71773088
125 151712455
458 4845266
970 19101281
434 55743235
77 207937919
130 197379166
430 684112102
540 108366809
84 304718058
336 141202891
551 31683668
726 152720721
208 115242300
700 454671068
519 351411246
925 45199749
467 44538794
999 549736770
53 260181213
659 393809253
92 47920100
192 10540108
745 158674875
990 484126362
716 234958371
87 14027755
364 1517574
161 38667030
26 183745051
108 299819907
461 1120155
625 8026387
390 73546490
760 38098945
388 128787764
232 113280877
200 454504503
825 300113034
689 106107736
197 609774529
512 20831364
465 82549176
741 113484951
952 262683106
47 395418515
664 19915584
367 211092543
609 1000000000
428 42066782
316 331561074
663 16306617
169 131086458
63 118929645
567 312089421
13 124075043
271 1000000000
433 334408537
96 303904904
50 502703796
339 266399875
120 91774234
351 130284143
644 213592501
701 222414036
774 755812260
213 12414977
637 117966222
238 288461855
82 124533489
112 257284099
813 1000000000
941 121293801
205 35662865
810 19760105
282 1000000000
66 255149105
542 209294268
771 3323616
174 164704731
821 1000000000
36 26854303
321 988046246
456 59915726
415 73952875
450 103241721
742 244134376
673 360194422
343 1000000000
733 105858042
617 7770545
607 265701389
853 250090760
231 1000000000
442 559281614
308 203543820
313 14707397
255 337550300
834 1000000000
591 1000000000
796 587836269
101 242593464
335 128579696
408 193759391
757 28870643
473 327924123
707 65371160
48 157687775
948 328499157
964 16014230
166 23305126
542 105907030
617 223496839
397 608294159
862 111924425
530 192540053
669 141801094
844 202785060
181 149649861
668 961414914
551 315924294
10 483359154
130 236533298
813 236638401
599 92899809
933 17677117
261 856633146
308 56354474
597 99805
191 94720514
655 546376570
233 9913054
250 79413333
880 152612474
199 1000000000
980 189435576
797 1000000000
382 90684757
421 60507617
758 16685351
398 872118205
963 25924293
425 426359943
549 117459640
133 65923828
798 123351017
123 374629296
11 181948634
899 173377778
951 141211885
396 67318551
528 70714170
63 984841384
710 88708729
539 481481
506 317324272
17 9816369
988 59139604
208 48871478
107 101207638
25 92937575
312 506303689
924 12661781
34 224062353
88 1000000000
666 69141247
718 174513399
728 72428287
381 112793402
587 306518368
966 3922664
11 138644
224 526535
433 257802869
964 696020373
661 17415599
745 62584562
270 250516745
216 43916221
789 51891057
489 1000000000
769 95717834
363 115292578
11 184649005
759 47645646
283 185287553
260 323869103
840 1000000000
899 44080290
171 334566702
508 146496272
323 118203345
325 71995843
937 6790064
105 559310780
596 339473555
462 469114872
13 870382697
109 103304902
523 302498073
909 5414737
927 166118779
143 393362505
353 3094429
706 249300514
64 93910540
319 158108210
677 66891673
414 869787047
23 240360522
654 413960
927 249376550
103 87803828
100 252994135
786 55993719
175 155600527
863 1000000000
248 451675673
173 502157700
38 673623552
485 228699162
177 212525961
471 41280372
426 245086559
298 199443277
553 30620627
822 91433934
861 750007219
620 60266120
511 1000000000
380 131904084
735 189763928
717 9482284
828 3644540
960 36558581
118 118390843
668 1000000000
527 145944405
538 43017225
484 986206942
762 58251186
7 258600175
587 88691853
816 71152082
109 199610845
255 37904987
609 110832072
515 171244523
623 1000000000
940 18566038
78 1000000000
211 73217907
271 60256143
112 56589439
570 344177262
226 1356350
670 78596219
394 903813345
651 21213219
663 355879584
122 87421073
578 11346006
299 682083827
162 1000000000
981 266752918
432 121352145
905 1000000000
332 419118005
390 100652879
909 197123695
565 406028215
148 273119375
502 74316024
496 11535057
16 470696723
282 1000000000
715 25631593
217 47237623
889 1000000000
62 24762052
503 122948152
169 126095063
496 657932313
737 1000000000
425 97514851
550 615346508
205 30049186
42 1000000000
82 16858864
738 15745401
872 1000000000
105 56396943
264 248935697
173 822043083
50 103840008
38 8007718
165 323833577
629 189834217
666 91722721
90 1000000000
584 74047843
332 75100332
456 64064040
403 32180075
322 1000000000
441 543889496
533 29035204
123 1000000000
705 1000000000
500 113121779
808 205107092
330 99584474
167 71224130
829 1000000000
809 124313718
366 2756284
676 34612230
581 20639003
752 395255845
665 76928268
830 26361663
891 208020654
445 553015747
962 31614865
815 36064402
463 1000000000
457 75812649
618 157066855
389 240890342
402 1000000000
603 195260326
207 159557132
771 343330082
858 40598770
91 23017595
355 1000000000
174 464468302
521 1000000000
842 978537973
765 262491157
592 58432681
982 353185358
383 1000000000
493 113169161
455 184520441
426 64779794
146 287699091
740 564825944
622 560040750
164 52102256
963 51192286
161 399891371
26 76454233
172 26652623
27 124185130
796 118365712
381 379705413
626 65266002
504 382752827
845 1000000000
462 88703711
814 146118563
60 166239056
133 1000000000
269 11988728
361 4836040
887 24605028
179 1000000000
746 199205338
26 786618926
975 212743010
295 539684635
446 122138093
985 838719851
454 11101891
633 116256367
672 182359273
815 107215037
619 594282624
26 1000000000
384 86263616
138 267637143
510 883198790
728 272792313
622 320158208
580 206139177
624 8532397
829 5274556
115 32213628
644 77220961
471 13921799
57 9294734
238 881797466
523 24947199
925 215969051
274 448556338
591 1000000000
320 354548361
394 418184453
298 78920751
750 8658815
602 104588125
356 8676255
216 142919678
652 284958409
892 4738446
789 193872685
917 539434683
256 175259801
707 92100210
756 29535205
7 197664806
714 48419778
913 569083028
97 653263601
576 45401381
162 53198216
109 181156099
717 1000000000
583 53786375
961 411195017
935 237616395
814 130014857
604 170422242
798 449539377
807 1000000000
591 85937514
872 1000000000
865 1000000000
918 1000000000
285 76456068
898 689578921
434 19034040
75 322671839
369 513101387
594 46974642
818 10325053
982 191048324
52 318865256
248 75620110
400 1000000000
128 1000000000
269 462279161
605 4085473
236 41149745
799 73855312
220 685138981
312 532450537
198 217639373
877 347834801
490 132979496
233 63605216
295 646571035
378 99720487
606 294833748
840 226425822
246 153361261
404 282579454
960 51314286
950 178650444
419 600776077
693 269709068
40 128550663
193 16341770
214 721989295
396 5674158
582 178475009
531 69103056
304 1000000000
225 76994730
435 265720583
868 169560629
944 1000000000
372 81351426
710 325252654
42 173630828
702 14088605
78 114369759
255 156141804
71 97250941
322 124571855
966 45450844
135 24429591
266 770618513
229 321271364
156 118491348
229 73538320
20 80249443
734 104326410
513 157616341
177 34594144
859 8728554
157 520868324
235 13492245
555 49627432
209 3179022
10 143108082
412 3424141
995 22290458
565 73363055
758 151909968
83 1000000000
178 184632890
23 166075631
384 191260392
729 295429370
247 117106320
736 42310885
64 667849064
205 191091523
283 386469103
519 217886242
375 971433186
887 18937753
684 254776010
708 7454957
139 935428024
23 99193386
444 797123274
551 926995047
294 200642784
885 37313912
682 89783920
201 99866019
551 12804029
762 1000000000
214 102154263
705 99522867
759 8304757
845 264414275
577 61892682
783 559690518
332 27477934
126 459137979
89 49526278
899 188112712
192 1000000000
942 1000000000
256 1000000000
766 120328104
434 136237122
347 338330920
742 84513114
582 1000000000
99 369497479
423 118623047
209 26698030
949 46424377
257 16626656
217 227835038
35 112286896
787 311690581
750 57216360
458 74169215
299 262415348
534 946911276
1 23249100
25 6318137
929 255916717
432 130359665
667 401586860
261 378227651
462 1000000000
240 1000000000
202 571874012
697 898792335
896 38356876
863 180100533
792 81080787
994 16092988
489 14732943
347 7540958
364 94029577
850 120276665
585 20662311
806 312953690
399 242444286
184 157127283
182 339209660
207 13389026
911 57005927
324 123157619
170 100173125
806 63309950
46 121937355
78 61720764
732 160490869
676 17696197
827 64421228
591 41294798
932 217426508
808 303947024
967 586211131
390 210110267
299 1000000000
10 45750564
568 119431824
459 106029209
1000 300108753
610 22311048
856 4955697
703 14374127
427 187623844
473 173181761
870 324294341
936 246974225
84 141748323
102 24272745
939 12794769
264 722033788
27 183588991
241 271051064
149 445709407
287 106661734
849 51394670
442 48707996
790 107949817
291 25895776
805 437823655
842 155373989
645 81558485
286 148340265
319 843936360
447 16840481
19 295764831
727 1000000000
256 160857396
979 245268494
622 22095920
454 34532404
663 1000000000
542 115256873
224 101026650
147 56868960
100 96785621
46 48136863
265 283541126
823 753849818
455 61825933
485 150745687
119 8918977
137 13739094
744 6129669
858 83705414
140 253269724
289 9037850
376 630119290
454 86129420
246 401058992
272 155111163
934 89256685
791 195032817
512 86154615
620 76614423
930 228920890
495 50767421
663 5527389
495 292329929
37 194560983
733 23102501
45 804794629
632 188474475
822 163889853
441 260526489
256 101037366
224 291638510
501 160364110
716 143744
611 69123396
630 42899780
738 63399723
853 247897332
627 130894746
386 192605787
366 25001429
364 167996194
762 100439378
740 1000000000
575 69408313
441 77987540
215 30139988
852 145765578
47 1000000000
989 497450152
266 138051768
691 58214271
222 1000000000
239 130445084
123 151846828
344 77014346
546 1000000000
719 144641099
379 1000000000
675 13847414
13 1000000000
901 221887312
177 172533152
821 82209233
838 530661094
130 1000000000
717 1000000000
596 458195742
61 35903752
476 6542206
111 248161008
858 8807547
771 48638960
966 135481786
32 139757869
686 231155160
862 254757921
277 801347074
967 162708689
465 285010014
384 334149990
442 167661712
500 1000000000
298 256731130
569 212038671
630 699209422
647 53686156
328 986208902
207 80666477
800 1000000000
449 636512906
622 6119560
660 315241553
665 436131840
697 25866168
729 153821622
975 413634772
223 336524629
823 27223990
131 163251109
248 776700769
556 538605465
59 24033213
219 66529223
664 48884070
23 36094087
118 105068427
457 506177198
542 175136698
600 189912827
887 157068661
301 2268132
194 1000000000
576 474687314
686 1000000000
560 17132849
436 306989235
710 194346220
3 536806369
657 289489982
68 121866893
26 398310327
55 137905679
560 67508654
411 15053308
572 132532364
945 1000000000
398 455068412
144 3625673
93 87391628
65 1000000000
337 54528254
867 344365447
20 122535737
167 7165839
235 1000000000
141 175452678
609 227951593
804 32447557
76 879637013
645 187961062
492 272227177
271 82968526
610 53384238
563 96679673
30 126972003
824 106277239
887 322815617
391 32712290
925 166060255
967 185366270
810 111735569
953 180797467
92 179593327
77 95533045
187 112056215
586 1000000000
952 11493226
721 120961398
770 14094701
681 19618503
938 1000000000
291 1000000000
952 309162486
398 263696476
107 271609447
899 9094813
148 83957962
930 426565065
194 578989633
698 541425793
222 7822225
868 747307183
744 206910451
599 21251862
503 305792967
740 403234252
195 69884565
602 77105826
421 1000000000
698 14213880
77 632673450
323 337116403
698 117793269
183 470212616
909 1081943
587 126665538
741 372127489
353 83405420
539 5013808
537 2990074
703 193933772
738 404394140
232 139824616
141 353390
959 103523881
922 1000000000
171 4264235
608 49863668
805 92233948
431 542196698
612 244970463
376 534729280
321 6334905
723 303389259
923 127201320
575 59973118
891 220916766
133 28371955
905 158715376
12 224255352
380 1000000000
989 29091686
493 136347881
632 501359869
331 95250748
716 3227360
927 38375622
697 164959189
304 222284106
576 1000000000
39 585559617
609 530076823
604 814257809
731 479586861
14 72079001
655 200500863
765 45004259
829 72830
378 83343155
124 842681367
965 68640171
868 75464109
654 123300466
126 529617793
363 107932750
802 479155806
359 668985553
63 29104282
608 274036078
518 147065559
70 392657669
470 23413
291 70130979
200 212107308
164 595661156
428 143987994
435 385208058
305 606368716
16 1070424
199 130367147
571 9390742
543 416218865
779 935236145
721 376355399
328 196536483
964 238233514
947 1000000000
937 57609196
684 365202939
696 2595172
514 1000000000
80 451212974
558 46591971
545 205659826
159 1000000000
788 35622650
182 154822228
153 7326424
2 480529
671 132056288
692 5961659
607 1000000000
292 59880402
112 1000000000
289 15529037
699 18291711
588 56166317
552 44185311
908 175146706
286 213269426
378 130564614
333 20272674
701 174989706
767 139190527
846 183315780
425 25681355
957 1000000000
230 385933997
825 32492870
915 170996750
762 10939659
803 1000000000
730 130843482
740 1000000000
702 323606460
766 277805972
185 163041027
858 40191880
321 268459313
952 1000000000
630 1000000000
647 299353703
577 174465125
984 1000000000
770 316883745
842 46776098
440 1000000000
94 153224949
755 96198651
460 876247584
653 242707323
715 389457602
700 434435164
884 1000000000
984 161558709
438 274893684
514 397268692
833 53071926
321 13940589
191 1000000000
694 6542074
662 473222991
217 9254996
382 746967427
249 55262984
672 217696661
583 71801884
955 147420394
242 849802850
137 62259921
35 1000000000
863 87459159
610 206393063
615 1000000000
150 459874747
577 480075692
351 587102690
189 1000000000
998 1000000000
169 81020930
419 111269325
952 34829110
717 269355960
104 173413153
973 542510560
402 591429163
434 11027735
45 34787937
733 193344007
761 8553696
310 415838837
920 1000000000
964 95259672
920 487223654
344 296528132
833 133761509
769 266895520
740 165506352
944 128658611
529 5229264
692 1000000000
967 375276748
886 49474848
382 18333463
61 207879654
328 17043735
402 5279778
882 328751324
117 162124598
151 78201072
253 172167778
765 84430203
411 313772830
204 4510876
958 319929327
85 1000000000
87 496450804
272 199631259
957 155160941
780 156711538
913 53311616
426 1000000000
235 29536282
585 14058712
978 380219068
610 16301628
70 366999004
788 334155413
624 137516518
112 1000000000
528 287457210
598 87557834
222 61500718
757 13168141
976 88343853
117 28622928
297 334484031
784 186556792
799 131948404
547 67802880
306 799255
65 448998129
756 212663281
280 11876524
50 191679942
616 189068279
143 140062929
266 95053899
280 143645729
430 176929155
408 1000000000
59 10449293
109 451305310
882 375737993
47 21239705
10 517804154
343 116571597
628 252106346
765 76845098
143 76852011
760 658009526
668 245074720
337 155141532
19 81301749
543 71742082
131 80791191
787 1000000000
261 17155494
572 9465942
688 289133329
883 1000000000
341 112234605
272 284020793
643 428447019
354 61510139
451 303452174
282 179955221
684 153529912
303 282295200
127 112511247
634 1573946
292 369355585
250 476656851
650 436382820
448 26994292
178 239022630
76 272786149
211 225545522
525 122603873
782 33088722
683 1000000000
722 8556194
160 189187305
192 20871569
169 112724219
408 25866460
585 108187784
585 349816060
774 104176
716 49101114
224 94139637
208 45989982
912 80465941
998 432437355
326 281141120
21 168094412
425 54380783
710 17404876
729 885393094
728 4631270
704 219570299
484 172590186
484 112717938
178 107435299
85 275667885
945 480416603
468 33999193
698 227695991
352 214583499
564 1000000000
626 8336410
408 552719869
290 127365618
749 198393549
927 1000000000
444 369396027
146 13302429
413 751172551
474 23987058
15 456244871
304 1000000000
91 104030567
100 11510727
568 285791751
461 469628465
831 50386237
91 437550950
727 151647017
295 92791260
185 42317987
409 540145126
204 302836655
608 1000000000
666 469772033
853 40069485
456 314920739
976 50105222
64 121053417
471 590358953
586 229984951
397 37246452
197 156547186
576 40997433
698 86227066
961 96058053
17 1000000000
775 43788463
81 681756873
771 188646476
682 44390485
364 352112531
421 67629585
907 239469654
594 388951398
711 1000000000
248 274746053
753 640284367
888 100328771
785 577946388
721 116385853
934 10473721
316 131466894
393 59200159
841 177522333
553 232067439
575 1061313
551 57997487
526 118638664
578 157612512
407 109273326
979 104999557
34 1000000000
122 377345438
54 4990970
614 1000000000
892 134495801
527 979481487
652 265411361
254 815306180
445 41146769
995 1960008
151 313150821
614 458351329
163 66487717
333 100448579
641 225019287
115 1000000000
136 30383265
598 245767732
129 377320177
390 465646353
419 174552572
229 37506851
831 894526713
832 1000000000
605 65812533
378 358755400
300 1000000000
200 44760677
36 71715272
693 510640867
526 1000000000
807 206492010
770 738755246
662 1000000000
943 135486986
723 174149926
414 713864813
94 1000000000
495 36732250
214 29975516
553 21199468
132 218185467
972 14461429
623 521068546
657 30252514
320 96716001
152 1000000000
358 96412495
776 13451698
354 6147928
314 23328556
180 324925272
645 46759408
27 191985265
634 38475183
544 191861199
57 140988874
914 273038562
89 52906785
554 60975054
522 269159930
975 188652831
630 773233296
498 1000000000
954 132413214
275 259949938
201 1016136
137 52927371
976 73313906
180 330213213
906 211499538
334 1000000000
261 74192522
804 1000000000
433 173696037
57 169091623
495 6487721
123 555789933
399 989356660
250 268115227
264 52270985
159 43699165
19 46972798
818 371544924
711 167997991
594 49680615
389 713299266
287 11754607
949 519380037
627 46202974
334 12640880
756 158590275
841 235407551
514 1000000000
765 407317727
494 213120607
490 386582814
983 433316081
458 1000000000
902 93905696
667 1000000000
219 254906157
421 86033716
989 35109622
889 11476655
861 1000000000
510 108655587
530 911367783
78 7067503
205 31821349
334 712961762
510 145519538
168 291770626
748 327761529
804 77716090
999 52875270
10 22795234
352 177327654
425 79976326
775 86132581
137 7719494
123 445580603
771 145518203
389 224444544
319 355480956
925 79954423
492 76995494
441 237681809
491 73966312
564 851552295
403 341923570
116 66119553
461 385915229
826 247255913
632 1000000000
565 1000000000
37 21927654
78 1000000000
852 187074043
324 973175815
196 60358327
136 140593472
301 39075167
721 74211736
817 62245606
48 1000000000
237 87480441
845 197460697
652 78987580
295 483197144
956 444956198
39 249860224
277 1000000000
348 13746424
896 1000000000
383 55699803
53 145560911
79 75378108
347 218651202
397 25745733
859 61439109
489 227298311
684 277368598
426 28881863
831 142972171
776 58751509
819 1000000000
668 127738909
9 204417908
534 629927017
65 224979061
790 31761596
994 562257597
378 19189485
348 1119052
253 138954774
209 138935446
5 17677682
718 306662023
194 1000000000
382 69410624
326 1000000000
7 94350575
726 831387054
473 43645049
581 440893382
357 2855425
552 540596666
323 314647417
826 13645227
306 181480379
105 215685638
531 159146655
237 163968784
245 1000000000
775 157279180
761 207167050
135 58063885
478 151083150
476 1000000000
413 681207527
503 395439315
958 400463899
199 106152703
200 127152650
885 129229133
844 27600122
520 1000000000
625 416947418
89 1000000000
856 165167513
776 1000000000
160 400183308
276 20822993
146 1000000000
734 100378630
397 1000000000
725 5612289
362 166805870
842 1000000000
817 430764797
516 264858680
249 593581442
988 270699945
59 149012707
362 222161167
598 195553475
77 53017704
499 1000000000
621 622302371
569 190694337
588 316906865
17 149669780
207 8647669
723 3047713
681 408504864
382 337100525
256 361822458
651 33565301
716 305275145
81 88758782
918 409228128
841 1000000000
926 179242637
826 19556608
635 210025008
869 36251838
221 5991881
233 1000000000
174 277770956
847 665962413
764 57663002
663 1000000000
951 412927746
552 187428579
656 69808350
515 177035243
358 98575348
87 315691339
586 33637074
845 121365770
740 1000000000
132 28576187
179 340317252
869 177086103
688 152146535
872 709206079
746 1000000000
868 356041032
322 207784652
378 10025914
616 830800321
953 329907375
371 1000000000
770 5911354
643 30566184
548 97470557
593 25028311
208 25085003
477 33299395
365 562410192
718 672219124
405 50201030
165 8957990
341 163898666
802 281227325
751 420909643
283 286321197
107 1000000000
963 191079649
240 84323039
840 433374457
47 521487552
307 22154440
600 909120315
299 345257942
258 64261231
841 56844430
285 509447129
700 715972180
26 257815712
261 1000000000
809 98251208
259 1000000000
569 386243105
23 1000000000
155 124349192
593 398426446
646 26406415
896 1000000000
315 56383378
709 126048045
314 108289899
959 73948721
554 180846887
743 200550912
635 1000000000
428 1000000000
254 286177577
887 301295919
299 537008077
360 144661643
425 56458692
814 23622748
153 11630541
225 770184749
507 1000000000
218 116716348
318 7606066
801 354108408
610 35675844
406 30281971
784 1000000000
727 298751101
552 1000000000
983 305834366
209 1000000000
772 63730468
684 224050875
798 1000000000
832 177241110
759 291341565
998 137965189
972 170490912
262 475612378
944 986329918
695 36199308
192 1523437
537 1000000000
927 692510708
246 162518154
443 144116436
987 28598015
588 674552333
835 169361648
99 289438146
259 267251593
752 186057267
502 75142702
986 199679790
850 886750254
170 40683619
575 165621100
831 417005320
566 19897403
562 82207958
703 81218705
850 42038199
121 573749642
248 828864954
277 77027075
900 110378092
874 68237625
629 1000000000
1 87970803
916 300058305
322 41021210
24 94611629
396 713946201
986 118750083
983 45282023
417 135861933
469 21490030
910 290173676
435 56140355
545 106605163
92 463027158
769 664568733
501 98721520
254 18989951
409 413835201
722 95464548
118 368431301
298 384591345
740 58736915
721 701876877
132 174943472
77 284353315
446 77917670
174 399034582
313 70291875
805 29487691
310 1000000000
234 827710411
901 87319886
532 811336250
356 405185155
323 208460681
910 131081709
33 1000000000
345 253362196
644 1000000000
838 338374811
484 1000000000
956 178397278
554 566492
483 4301947
613 362892747
773 229464648
958 8913692
448 325534687
957 328434549
228 107102076
969 157893249
866 868816625
747 299996411
57 91006779
130 12099533
3 1000000000
527 491076141
685 63378132
194 458374793
153 6674548
298 134411185
895 71281583
71 176453417
175 171794855
450 1000000000
808 170436471
339 1000000000
850 97662594
265 427954413
926 784478508
829 468337
180 12060066
71 57234836
803 1000000000
277 375382397
420 330849980
194 67916652
158 39297571
236 66156593
634 1000000000
132 237084280
183 628333822
713 112941792
342 186630530
604 94121120
431 64902647
476 312889514
657 108963664
842 192110770
100 55770235
853 1000000000
738 29344432
630 76849055
624 40063182
733 225044736
633 587880376
545 170686807
739 21226030
275 1000000000
398 86608325
682 385437491
35 103763355
471 167477441
250 1000000000
265 403972751
714 218869485
185 29946257
188 114016871
743 279232317
439 755692345
146 1218155
340 155578769
402 338418
98 54852294
456 701653358
754 947303793
796 82439784
828 53145424
294 212890408
319 146816183
812 37473787
827 1000000000
993 341946990
330 1000000000
587 1000000000
761 71059099
698 493889030
371 407902882
800 74756115
94 103220200
346 75968223
194 1000000000
83 212500807
360 9119031
248 43354016
544 59044094
204 176442657
321 277474312
421 9373012
564 342756380
803 135172513
456 37637764
799 123559499
758 145632118
849 512504907
253 771616500
976 35507505
54 1000000000
293 49919787
865 1462474
919 411693078
925 944759593
463 132818971
347 1000000000
36 283276363
650 734354941
703 96456765
187 14015761
344 605082
389 81836012
166 112559689
729 162534951
394 109481548
198 23325379
619 1000000000
645 299710285
874 1000000000
134 342708153
590 250805776
152 207172511
864 27537758
28 302754318
520 12970155
201 320766020
805 350784885
768 849449138
359 669035642
320 9871755
568 9240311
218 85171615
405 143996821
614 808426882
49 607592746
203 64835141
202 56867003
74 47723453
320 1000000000
42 51999359
764 4216419
500 390004508
110 998069648
967 1000000000
533 41311509
428 318688193
473 1000000000
690 605142444
940 1000000000
290 101621575
564 219814750
516 39973215
177 407323100
479 90122797
260 75808422
996 114824555
108 241438266
866 53296058
490 12471421
514 60278883
998 260696367
147 19876365
735 25232899
150 244833701
446 7284421
531 749011526
898 179081571
225 13480630
980 26201837
449 520222180
188 43949778
754 10150589
937 444530176
325 865763666
411 12475086
601 27853585
371 557798713
591 985065430
865 46199221
615 8215919
220 416330011
320 95407137
173 454515523
58 147234393
988 7536860
30 96514444
335 29513797
524 320460837
385 83542719
347 136830680
40 39555057
628 126392488
749 10615757
823 154947255
431 1000000000
427 1000000000
55 1000000000
88 1000000000
748 398187606
967 36643545
399 1000000000
424 304034544
919 1000000000
74 1000000000
901 685596773
334 232754242
673 76713482
419 115542654
10 1249260
522 468660664
721 786993282
451 340884382
85 244859043
877 15302407
207 154163169
656 1000000000
950 1000000000
589 968281090
355 377435460
356 70633862
334 1000000000
860 1000000000
822 1000000000
318 236933659
139 385205298
994 75979641
310 215107963
943 194258663
887 819600842
557 1000000000
582 51738392
501 488854182
369 187265014
287 90992639
403 91346475
650 365324939
666 18940001
519 814332063
822 82714177
381 242485443
225 104188211
213 5130364
552 236454838
151 121308142
286 478127952
34 160967020
672 1000000000
286 18828135
297 239427181
997 137858789
879 432871273
372 153840623
42 100033863
70 631546234
171 193427703
144 89337495
426 227811420
637 266431750
686 152805014
891 1000000000
416 82972766
994 10284169
351 597504302
627 184697993
148 135796420
598 1000000000
238 191287576
266 169247392
502 580742281
224 1000000000
508 491727293
431 224579052
287 371496615
680 204863343
72 192095173
907 263655240
558 248021294
95 2575799
690 6835589
268 326572486
827 14426584
996 1000000000
626 305436049
564 28946414
207 79044341
951 44870013
249 118356227
2 45433097
808 386269232
712 120093934
870 267829139
623 107900882
760 151165395
239 123006911
841 101758304
922 279582449
503 209795577
213 1000000000
842 710406489
106 70569794
635 237223
777 174214583
498 55681915
42 344779792
374 16873475
11 4985784
151 446968380
247 402723316
487 105793663
188 213565752
476 72188876
219 30346458
414 450206381
931 201952620
702 83165067
316 151295188
523 117794
152 106800732
974 37573241
157 26521137
847 14046270
963 79687889
253 204972014
315 425155012
737 143528163
229 216213609
850 92690845
560 171746379
425 41188660
12 701630587
118 461087784
978 156478114
256 76858583
690 532791911
919 166099543
228 1000000000
708 329348289
959 216000513
647 623911346
307 559195803
127 500148288
241 19552141
149 358142637
945 476753058
561 94803325
34 1355974
753 419575713
669 3168469
120 14181575
729 824090084
380 16660837
23 203143018
374 31288389
518 2511166
573 69386083
391 275615855
330 42301457
666 693851256
980 659385300
630 193697565
780 136435418
451 155257630
809 101460544
75 115773232
492 361220463
747 97657858
709 1000000000
366 23195128
371 279387344
194 205772439
311 1000000000
463 117335965
976 93980997
726 79694604
215 19805897
879 121692082
43 967278423
393 123067418
525 120661350
381 15221925
837 1000000000
434 459635944
906 506725996
641 1000000000
124 82814329
65 637256180
372 370069418
35 40279023
714 339513118
535 4112153
926 16325512
28 1676291
790 878055948
338 28991427
237 314508631
619 107804533
465 188124650
500 218354239
226 100004896
496 1000000000
522 24278581
941 102305515
518 20299935
211 352275404
553 543170794
331 393920973
64 30267883
941 1000000000
382 68387564
312 909280685
633 1159300
797 1000000000
761 817758050
219 254564946
623 107097813
643 13945160
467 257512731
716 202900590
932 725205089
415 211747210
707 22702321
276 632363838
103 268133632
826 104153303
961 156139413
306 1000000000
624 239849864
203 62740854
829 166813487
254 320446405
704 9219111
706 269814038
320 65512218
848 2549974
486 6191942
103 10044363
945 42282927
624 195699864
474 428746356
451 146992978
432 541220315
495 83878796
260 1000000000
333 296092004
70 38068797
852 413380127
805 87750512
909 17603685
969 329618955
279 61678230
444 64422170
467 30757775
787 170688444
169 20373459
33 910858391
504 75427588
68 296235011
57 122290271
764 321393036
107 186805221
906 8207090
183 1000000000
110 289807497
260 183482833
895 22118055
43 169355165
469 78749261
387 238737254
674 22193862
109 17832836
948 105816464
601 247272564
539 127856364
942 492102308
624 71727341
869 1000000000
330 284167175
629 373615667
322 643407578
567 44455415
176 275891452
787 1000000000
547 37668469
959 116071050
892 154944320
230 324598441
994 36967079
294 5897595
326 69916470
728 378381780
832 145199843
427 250197917
439 512033372
376 21111876
491 425393146
806 4488449
725 161383416
854 20923708
805 51385539
392 551949265
282 298909738
283 151332922
13 117362176
903 186089017
718 63272045
653 266307045
979 15341854
797 11314596
623 419996878
958 102865113
472 2941638
841 1000000000
247 381206180
22 290400311
363 118466503
780 99816204
717 7511773
147 185924478
972 323601970
92 79626786
481 21459181
631 174620003
227 74948425
179 1738613
75 55108529
673 1000000000
25 250996817
208 75251499
260 37797544
721 13886003
141 151500245
148 1000000000
507 166950214
464 11436485
175 55429609
141 47239642
832 49437961
852 5242747
663 263411358
893 67800268
588 17286679
239 1000000000
598 922638172
443 338573121
397 44630385
729 104806085
706 171531268
88 1000000000
37 70636155
88 412676304
918 63878393
394 605207551
11 1000000000
846 335182507
679 84569876
987 563390104
200 373767000
858 282318000
334 9235622
66 13659387
659 138809202
620 456082175
740 464418206
264 308113014
868 45944563
285 210684240
896 76600070
59 628883050
875 199626715
284 119505895
323 380658709
93 242665868
544 39693521
969 501854464
843 124843540
29 14951869
4 1000000000
868 92110214
658 395326042
364 119757763
110 160848549
477 47438008
431 18951920
248 237485381
78 96990262
173 1000000000
602 431756777
307 57520572
709 24667665
659 19347565
476 443089145
404 1000000000
57 116035274
159 307323017
892 179291649
772 158749972
244 245721383
834 293374588
530 6039981
577 229378982
349 200742949
75 411865714
126 404703153
221 1000000000
581 67674246
834 51782181
769 217666818
471 3211924
379 483950081
919 380314540
322 501740752
408 10714281
878 24084650
674 410598846
377 12004967
639 16833345
33 112959382
436 1000000000
686 160353785
851 7391042
89 47417634
244 232768127
18 156216962
223 13172509
696 27899527
874 32264937
876 321992857
768 6124607
157 64585887
207 17776035
236 27042352
256 183652721
72 184261011
362 218563302
418 493056310
909 44413670
865 139855090
363 49625209
558 3965658
346 272277172
833 495966489
434 1000000000
281 188959484
468 161608174
119 157333307
136 119704591
978 304134
773 1000000000
339 15376018
915 271885551
866 96023332
468 329520
726 1000000000
973 84607631
711 291884722
321 20311685
366 148041927
318 1000000000
659 597764785
196 12941023
845 1000000000
340 141991107
653 20831925
798 121530827
395 551375545
617 1000000000
750 168801098
294 91428435
822 190891893
268 1000000000
908 728563027
316 3626417
256 299986590
389 19082975
425 343504170
328 163449407
776 795903147
141 394214574
100 9676287
955 101064734
486 31663259
474 243197230
989 42123855
204 170220855
306 272733477
550 525345455
333 235166010
179 45973882
541 452482863
49 457014943
419 37138978
240 42309178
870 92390585
593 862324857
175 290051340
756 70617648
917 248955598
64 10801059
721 58811189
750 109095781
403 4196444
677 26556614
498 1000000000
654 7791686
342 612743245
544 264284267
393 288155036
828 8609873
360 14010348
154 518010732
254 185991070
409 60920444
688 61386761
153 392573173
849 6133001
748 230943758
15 501825081
784 87796630
258 4803547
85 85349154
436 1000000000
580 396465215
242 13585575
300 920375434
7 93063195
998 40413588
808 18711186
682 64364857
856 122147378
319 549876372
245 150262624
102 191965550
383 38153587
606 1000000000
47 19863570
464 234156445
333 1000000000
171 3750997
840 286492315
96 22173675
529 1000000000
879 148164959
327 46115965
975 57657704
555 11726132
697 20053282
669 91032912
76 141364521
156 8933055
57 20934043
488 487783
303 340169819
34 873106923
983 298499122
354 61883076
752 91474328
759 92539143
803 14390754
18 1779527
960 248443912
770 1000000000
854 57742152
976 73210116
14 292676678
900 156234957
7 258045714
637 151039854
514 34275979
596 70860337
38 321907063
584 45410755
900 121460330
889 156461020
212 207067270
273 11706197
941 17644822
702 30342480
96 1000000000
776 37287228
916 9478774
784 1000000000
690 239564570
150 500525458
481 325476150
401 226911840
482 705399100
250 390153087
924 69067600
456 26251226
200 29299458
308 750720652
822 26459619
901 409692547
421 296760506
772 106388138
622 41486833
616 210121361
632 91376061
658 455884196
756 63905495
122 1000000000
42 136396151
207 304309009
280 110207970
978 1000000000
977 1000000000
210 52251456
627 269107339
232 732963334
39 1000000000
492 126365050
268 5513580
989 24377631
467 47759765
411 192834934
379 189433355
535 26220303
461 50841330
697 784058388
489 102829943
128 207223909
262 42736683
469 486991515
892 120265031
232 1000000000
516 156270
888 1000000000
534 236492115
341 1420964
729 699013
752 417891303
942 24733491
609 272691939
469 1000000000
599 3670309
941 10144564
363 12112912
190 202955385
348 653320483
449 91170539
899 228457210
486 2051538
231 294940637
972 105206564
641 81382339
748 417296697
169 1000000000
213 54386581
46 1000000000
336 33843992
305 360693782
669 71723695
897 79311552
731 234270731
511 208328423
858 186160223
82 38382007
803 79851645
539 2709132
398 329823703
274 148351162
794 100581450
134 681131387
456 3889967
751 593297914
344 1000000000
191 8694959
529 45686357
179 1000000000
275 134790503
46 290808341
287 169468941
917 503515625
149 344392973
67 60990962
292 67710418
822 231991620
357 1000000000
214 15099875
807 88140932
685 56988664
987 865020173
728 232253832
345 34033672
786 809553938
408 171247402
208 595276509
312 645868460
493 410166442
683 7106649
287 116505169
342 30524485
454 1000000000
396 7570476
131 315189735
2 149314332
286 4005759
747 242262487
294 1571815
597 864218048
180 111551039
72 157909187
167 14512335
429 7428146
8 157405029
828 99780511
751 646914
548 53056892
771 1000000000
678 0
860 162297907
57 621615030
923 86985661
734 14885484
112 222954134
741 787566739
474 129654332
429 89796673
106 7481025
790 484226114
775 211447102
58 136167626
58 1000000000
406 10355655
491 38992287
453 218337262
313 187377792
653 1000000000
293 279379533
38 151081862
894 22514650
201 565759975
244 147501959
477 159167672
513 1000000000
356 365920176
155 139540487
19 64133329
458 412000924
356 185258269
983 111783949
591 129412463
2 104346547
556 1000000000
786 1000000000
289 166405482
384 176081340
529 391907336
907 637827208
506 289100811
788 408587394
333 221053479
50 131608895
137 72921549
862 461210278
126 58365575
23 268525294
750 59191032
934 313478758
207 1000000000
67 38301955
17 19085698
781 16605890
997 328136003
893 147163722
971 1000000000
914 112240355
290 362646
925 364709686
506 34902170
70 431935471
813 216309045
396 102775190
416 191822793
679 436194804
238 100011454
120 43153611
37 418324054
311 40447613
397 127891926
187 1000000000
359 21909875
5 367077188
603 18204558
381 266604089
512 292910931
762 59119105
287 275741518
668 249888507
983 854423989
692 187241285
321 144278195
250 375629630
44 477871378
157 287528868
745 46337322
846 76912332
584 232256417
148 1000000000
496 704165123
344 21678216
417 1000000000
409 21560971
813 125524382
200 90673712
321 142570669
365 249101596
8 335230181
223 83200380
448 51088084
983 113014900
625 59930082
412 328677149
988 78773305
967 645188409
329 998301873
271 256558241
967 163457255
357 497984616
975 441736754
73 1000000000
912 72664190
114 407373850
667 22551368
216 96623991
735 38525977
933 103944839
805 163538229
974 262650164
741 7609549
758 125333878
486 205416400
586 64582280
737 515212327
781 15284816
101 5075433
141 15203979
747 950239
938 173506122
514 257217328
422 133252517
771 65017378
918 369367764
245 69874474
381 73745983
209 12188131
72 28514619
311 191015398
402 22499338
358 145079094
81 79390
263 1000000000
309 55234554
937 13996908
279 198759234
197 33268388
871 6715799
858 1000000000
956 296964466
153 626370766
191 74375749
610 74662018
415 43124535
12 91267575
525 51344595
880 1000000000
601 72469200
133 840949005
298 32539439
924 29390612
952 1000000000
420 38158607
92 2906367
998 7346331
302 67788923
585 343105107
349 17005978
158 27653839
490 268846465
125 5686606
532 1000000000
13 114655503
12 28351194
15 126032122
602 99793315
514 984330192
637 101059156
23 165449626
126 148096675
925 21208492
988 21086780
557 1000000000
863 30856810
647 2990517
305 33840828
322 395738569
488 215718571
727 1000000000
900 103744248
677 24617322
942 54036311
77 266193327
886 75633184
470 185124443
795 16025192
993 459681685
214 1000000000
509 287253463
862 320047308
931 434908461
236 145723258
803 404756697
511 11231696
964 15885932
600 30351392
559 306063513
238 1000000000
275 146541538
227 919930948
313 401400
772 376624995
201 76479101
723 406210857
826 154734140
480 30748974
556 310667099
850 193653370
600 103302911
482 134096047
214 90005293
240 440892356
573 74870481
395 325620400
182 22906097
883 287713911
512 114629188
809 42257150
276 324380361
605 8413647
898 1888165
78 872347925
233 430860416
141 59088681
897 4362435
882 1000000000
339 154659552
980 133677254
175 19147722
827 505855872
892 1000000000
288 302203453
603 1000000000
699 128971100
908 158197269
251 66110758
334 155546967
561 147794471
913 148030255
100 1516013
190 206719876
341 260682709
13 439770171
739 194052225
413 532145332
111 899564943
135 70770285
241 430909487
506 231827576
176 136718746
319 257473246
789 1000000000
742 239011862
7 116486442
734 432163
871 1000000000
959 367334341
572 224491048
962 683174318
719 4089982
687 707696265
448 41803685
725 314089838
270 351457948
701 2820944
585 75792283
607 222975194
995 60686905
386 291809537
921 645493447
214 1000000000
886 812477944
892 244692
287 426360295
500 50821373
199 855779063
669 55123185
932 135561303
936 315381111
943 335110492
716 87908418
807 49169174
274 591386322
972 489215613
306 357439352
96 286331564
883 125152585
696 236066863
141 144757385
335 348219970
2 266802334
91 246861820
663 61422893
780 107520697
79 123731734
99 285073483
967 123775921
456 66499289
218 246610003
42 25657082
534 20779011
546 114287512
643 94390855
119 568683473
570 137431802
186 664444937
923 2443690
331 341296742
437 249059020
241 31561577
289 554156165
844 15414414
174 251166515
973 79512017
517 19062970
652 82363614
454 1000000000
176 136553703
856 280788874
474 983701507
484 111429153
449 70263676
689 81888852
102 189949733
431 107897422
737 1000000000
232 337549812
689 539495648
298 96717117
15 220731765
773 103881558
562 134125549
26 13120425
826 39996377
560 46781293
153 3136846
113 287991458
701 166422166
466 38827
126 51401374
181 52641584
453 1903716
786 136200908
674 1000000000
585 122368079
468 83764705
376 1000000000
172 108158783
130 8657840
673 8105747
781 1000000000
956 30163818
18 1000000000
668 62532490
920 113966452
858 172444581
567 103400235
101 555651662
857 494105300
255 279557490
668 127012349
453 314810218
728 458331134
873 757530573
566 1000000000
195 40903150
310 106410325
906 1000000000
583 46446703
447 10256137
281 1000000000
410 19718808
622 1095975
114 596642904
595 1000000000
671 21377460
179 48003370
874 5460211
292 198802898
43 196787205
230 34943836
937 1000000000
634 73497851
613 151914441
680 292960434
367 54372075
943 227514850
398 45181684
336 7360099
42 211499409
410 1000000000
452 210581451
462 31012996
476 1000000000
139 359107510
865 731794760
362 184129411
868 339442858
299 921495934
796 248342720
557 2225689
122 8761918
872 6498310
693 553832445
622 269428440
934 2042718
828 12032905
957 145645403
725 1000000000
313 618768899
199 117001370
539 200668495
210 295573607
18 1000000000
407 37499919
751 323173972
270 478980763
969 527152720
422 96312294
593 1000000000
728 444215
231 322773606
963 172098286
114 142663588
768 80246339
810 91515051
94 23746999
233 111841642
542 292479579
732 60094811
440 494533110
534 61711694
603 1000000000
388 716915230
56 366811261
457 19232566
846 25552412
891 1000000000
870 152053959
35 1000000000
295 421341745
392 1000000000
594 279172040
706 46402407
622 239514408
723 1000000000
772 216546010
688 807270216
652 1000000000
564 247078393
261 82969568
581 753473368
528 1000000000
947 470442953
988 1000000000
903 285817222
506 1000000000
521 272433556
193 7272518
200 207272413
258 67347832
429 81028542
173 43954701
975 0
857 1000000000
383 228754164
807 154701206
941 124155672
390 25290565
112 316063696
503 293585174
456 256413655
305 446278712
70 611729686
701 72448081
570 1000000000
850 719378793
987 573630365
193 22240466
234 662370590
562 121236174
246 700676281
268 162428526
928 117721749
448 354108492
448 45288517
237 492372597
725 1000000000
244 263868328
656 204204524
236 1000000000
576 1000000000
742 13846577
133 509970909
818 288289166
185 1000000000
599 145923165
810 246815212
990 35196574
632 598692200
526 276349175
204 1375593
856 369538016
702 149585145
75 115854374
93 58506920
864 524129583
898 703251352
990 304198065
604 65911027
183 364523657
108 5312434
736 3482341
233 141841036
531 19744679
140 928880372
728 75890409
772 151906583
518 15808466
627 113177380
118 301088551
118 1000000000
240 39813760
775 98955353
931 4436391
470 96239303
199 13737425
610 512968057
749 404308876
556 980938017
269 144031651
748 1000000000
934 27651013
17 607847672
153 73331321
819 117403413
29 209335798
323 228434655
923 614804661
833 203181524
35 8331571
980 565866309
924 57503339
125 21063630
598 1000000000
108 19983277
394 4029340
952 96789171
712 34621339
185 12751598
167 46702664
616 13070782
784 36094724
885 409788657
771 32150986
735 1000000000
295 427129090
95 439826031
836 68985704
644 329350310
435 689629036
303 52339442
324 254454432
335 984264325
710 469685563
405 401770656
434 10895833
833 8322508
591 1000000000
458 6656874
990 58492019
33 42803008
439 524221105
5 603253739
913 545528841
983 12466133
716 567548656
854 55343523
481 165035309
123 250919762
928 1577593
430 193941476
392 103378086
350 420241774
498 1000000000
107 359098538
118 149052849
679 1000000000
427 239240378
943 263068028
473 284384868
590 115418749
865 2999774
898 88512950
163 217773152
571 1000000000
902 95927357
762 79691912
523 1000000000
887 139009434
153 23651915
737 34650053
769 90971152
680 90520044
315 2383787
798 1000000000
766 84612206
688 109384691
666 160273514
969 479771444
833 495063848
463 1000000000
840 15566780
594 130299360
730 5743631
619 43827105
932 520048389
858 89892383
737 12175069
302 1000000000
271 313737
768 45730179
854 170167554
903 1000000000
503 25215526
708 1000000000
938 201073
311 369430914
606 1000000000
895 178785421
204 60425466
428 204286823
523 1000000000
239 86300115
316 97870450
992 517592381
159 606523715
174 543850493
211 220218433
162 1000000000
777 262961869
139 38534131
680 260791493
458 40789109
544 764345419
911 16617098
843 1000000000
681 172241235
887 304740316
305 1000000000
84 421474696
302 260357046
515 200043506
113 1000000000
435 463999247
505 23878051
726 60187265
591 163211432
793 773884657
770 41307931
862 3214663
27 157830507
29 178260807
530 280903173
846 1000000000
478 73085531
112 124212940
976 608245222
291 1000000000
215 24669808
88 46160928
380 199394840
711 196022538
54 68930334
263 314542
94 828009295
129 206489553
275 1000000000
28 620602632
311 97068304
457 58752338
935 348030804
343 214146728
229 95008116
39 51128907
153 186004024
369 70611563
370 279836
452 240596929
625 1000000000
96 155349226
678 144168870
567 34569906
944 428646955
510 262209358
359 88321809
352 231856397
28 111608714
267 530408608
423 32517105
247 135705
103 305834239
85 8282587
493 914959333
677 669083003
401 114309682
598 1638638
242 1000000000
897 5618573
136 1000000000
909 61849488
532 1000000000
643 1000000000
622 298213292
362 321125140
237 182115569
531 79351230
202 13615035
830 41125444
580 108887752
154 138134098
996 444020983
479 9296727
161 30413186
751 1000000000
868 56643685
31 29556680
397 103275391
322 223051602
979 350575775
774 227298889
199 83198436
347 255252743
440 250754032
986 458218428
183 263467723
227 296856459
339 620892266
181 77858570
61 738906471
33 54596733
917 2014033
750 40836705
602 21284300
861 2397181
524 445195741
525 122398823
877 42549553
463 5864875
18 46763244
347 29931961
430 200133268
968 98473700
647 19733604
303 530060188
933 1000000000
911 44623498
857 358598883
881 1000000000
771 157409471
732 1000000000
986 380474858
529 19598326
142 259975278
415 1000000000
825 374768590
535 95695989
808 62848533
705 596232818
342 134100277
44 1000000000
713 148131234
961 235887088
73 162330273
295 181433506
663 293330668
183 408720676
115 281175665
824 171479526
660 35310060
67 155312427
123 78220687
800 389258731
655 798781991
742 169941351
473 1000000000
214 1000000000
505 71977465
391 40145374
942 17297971
802 214354729
328 190439570
462 1000000000
952 452664875
380 242310355
734 1000000000
395 139374150
953 34364837
100 39456061
346 587827557
703 136686915
176 365469871
203 5862703
492 666296082
161 57444175
742 1000000000
872 199792794
469 268119684
161 944930191
26 223304492
659 1000000000
44 52885120
439 97906435
356 1000000000
493 1000000000
569 777769287
580 1000000000
876 479543314
285 13926879
164 167347534
319 96742504
610 59784324
563 580788154
78 295968949
816 248304660
391 60645216
79 435769091
390 16041954
511 4579704
602 769538976
426 106934884
428 9878883
941 58682801
859 537724280
922 486052420
672 765321154
857 149352433
738 2088535
249 22489524
659 11864888
947 246727484
80 1000000000
583 94232512
723 11112733
724 17641126
868 453791634
826 81027980
202 656615325
458 1000000000
726 443210328
12 102881602
368 1000000000
55 102360690
111 5608367
284 142143169
835 683549517
682 46819784
861 120740456
634 1000000000
477 277410573
604 355083100
178 186900265
871 1000000000
949 521472100
667 562452784
118 8775479
97 221365922
276 226098378
641 700274624
935 17342561
226 1000000000
368 131902214
13 42739839
447 190332567
994 123964180
259 3572175
976 1000000000
349 113611981
735 114354496
804 43997921
872 300847144
321 22863662
795 43830264
579 313318519
439 171094357
75 162951728
565 795273726
481 289938055
204 582154038
740 53567942
197 261001656
389 535927949
88 63335555
515 76766877
948 223485267
215 215538795
993 5744886
120 994022144
536 65526625
711 372398328
369 253541987
660 21171771
972 144250399
358 85553646
935 125892059
765 2357874
741 1000000000
11 77743060
36 118061418
293 528162858
716 199615861
190 408949230
70 361479794
300 68935776
378 1000000000
279 1000000000
663 363314862
272 1000000000
686 8342936
335 112492177
974 912931192
451 269613654
624 97930389
844 226335313
332 406986107
356 39467070
945 314503266
704 92389265
231 2499850
755 98605386
240 1000000000
947 1000000000
217 112076793
840 72019474
749 39460055
459 292835805
953 605589308
604 5596438
528 1000000000
458 140031473
400 34302144
630 88106623
457 58158653
495 391101014
244 244357510
134 154987309
833 1000000000
843 88331608
111 79928484
269 222065713
991 574860222
820 95001664
257 17363705
505 563167677
339 33804590
732 40799641
912 395400593
140 408250041
470 1000000000
634 117598582
542 589688814
293 16325498
911 45560425
934 32922311
321 1000000000
173 67644868
422 429910382
929 468114582
148 105212783
387 164149372
371 75087748
730 215149710
124 205284923
791 9907327
414 401517875
345 555558226
427 111108420
401 63849995
136 552674119
174 1524540
431 1000000000
89 305174015
912 182023699
986 281567963
163 1000000000
736 189567875
439 202041437
964 521780214
972 314067820
477 54896348
115 81598239
76 47775187
868 327079506
16 639500679
470 41663583
962 2078707
938 253869682
785 123794738
599 156514771
351 57304462
110 937361090
857 49062053
126 32978768
145 54348529
600 1000000000
47 1000000000
820 189265725
434 551526214
17 127816036
939 1000000000
559 170544864
170 201642599
40 357697841
486 316468902
105 392119045
567 20649139
45 95599216
470 426580325
530 36134967
235 215935473
8 1000000000
693 813690371
448 795996267
989 101743342
794 1000000000
979 1000000000
925 373954572
446 91651625
314 1643422
774 172708243
544 982965945
804 538831108
760 854127985
920 346222342
353 197416870
489 100692053
884 19170865
952 830790669
609 35597888
100 1000000000
583 595172407
678 444144152
518 37519803
853 205610536
296 24130137
290 447057771
434 179033045
765 983966347
119 155850264
453 192177355
189 1000000000
475 115968247
436 73657442
310 164197653
645 37132582
311 150006296
880 67334986
189 1144383
204 929900981
561 81374306
386 627947304
651 19670835
369 110527896
66 315573945
994 2173078
662 19553028
780 1000000000
569 13730875
704 174264579
176 1000000000
894 60468785
598 133626013
357 111404255
369 42547446
470 236178710
481 1000000000
160 76779970
295 115286579
836 172590642
739 804834104
249 458310125
988 68501744
480 79528245
146 495422143
488 143096390
511 52087770
666 7204546
208 82656973
894 182222807
768 195919398
515 540024574
773 123308260
154 8311368
975 3033162
570 145961495
367 5170848
420 1000000000
917 23863519
55 177729612
968 200540253
60 28485809
1 1000000000
819 446213381
623 166916117
715 288297369
235 748134923
21 266974006
677 14120773
576 13547778
436 476266069
381 44757012
408 7208878
523 187238542
834 468421181
635 25868485
66 304543887
164 2344854
375 76364713
639 485622339
290 233122359
772 240174702
434 170808352
698 123041191
816 701081455
666 13292522
20 867046912
475 579478099
237 358298107
558 710142344
476 133076674
386 479146524
160 193315237
696 423117265
98 66073702
848 78854145
9 499225289
577 408820713
790 71333620
692 497364086
840 100406652
208 66430362
656 1000000000
254 1000000000
286 1000000000
349 1000000000
609 462756315
302 184574748
106 265912273
361 434570247
320 197570929
213 440537332
20 1000000000
298 1000000000
157 235780394
537 159196317
84 284199236
594 221471630
560 397718681
748 789322483
27 129059831
256 190070865
330 233005684
862 1000000000
759 47676451
165 401130173
914 378275485
133 683038695
178 1000000000
223 168092697
376 102882825
99 2830150
636 7419886
688 142265736
965 70892495
303 672728614
987 231405713
271 83018756
399 427357612
553 181491071
481 56475085
13 72563104
632 334301692
786 27948722
325 1000000000
752 945460063
456 166498599
720 47259994
120 990257070
218 174028151
541 9700934
117 19140006
568 17482313
658 1000000000
705 88743655
865 81517251
663 119220996
209 130922224
227 159951249
746 66541577
220 404923174
173 188002079
683 27056817
194 6402666
143 1000000000
776 219763133
153 1000000000
200 39899583
929 717059197
1 603664254
366 70360679
860 615399459
721 1000000000
617 167494850
497 1000000000
7 476931645
815 706688300
174 139321553
74 261261779
608 365003398
987 188967180
882 56296634
474 1000000000
191 360928534
870 4155111
260 125163316
287 1000000000
716 30281116
847 271117627
925 1000000000
387 1000000000
103 375305552
62 415496827
427 13743900
358 230654209
129 185431106
603 1000000000
744 312316991
726 22377233
649 1000000000
727 488683753
683 52930485
397 37221415
823 97048192
576 210934673
189 85926408
10 899519297
148 116529205
104 175789275
604 245543031
125 269010583
663 131558663
407 648955332
474 36990761
822 115106568
488 1000000000
243 437013692
998 12382637
462 204757364
103 984779067
822 437528014
273 376850261
540 194405330
100 82006333
823 226835521
17 1000000000
808 65081507
376 12314533
39 1000000000
128 784342916
35 287004256
146 109529530
948 8284826
358 431231133
347 453892041
802 38081166
400 14021794
609 150758081
962 389848250
145 428902229
474 12906138
875 562541153
655 126049961
454 436316162
802 52905869
330 1000000000
827 73131479
257 458751982
641 425920982
545 1000000000
125 50477622
578 153561603
534 56097492
805 394504
917 370777496
337 100735779
89 267479195
264 65121940
443 17085641
703 44512268
554 5022565
728 63922464
871 1000000000
51 124209441
946 134165388
504 503631118
618 29332429
334 52064558
752 1000000000
813 375480798
691 214994806
166 248893849
612 115710061
737 33361107
570 6322036
325 476225524
150 25330077
179 163709096
31 62147255
762 142410947
815 500685412
651 1000000000
259 1612853
829 634655223
565 233188454
73 72752952
413 640955135
119 89066273
866 416219091
390 1000000000
21 769671951
806 438092671
310 292057932
849 13667580
516 15815216
572 45850207
831 10577620
978 161611701
528 441852105
697 3982307
487 261839586
641 26699615
83 1000000000
779 77140791
261 983062901
527 588135075
229 0
268 187088331
698 267681018
67 121384966
396 144361628
227 1000000000
756 290291721
325 303974629
506 23123016
128 870460876
717 851903512
437 1000000000
222 37630149
380 182845247
20 279842442
916 51351251
848 1000000000
693 58693882
129 13146221
233 4281339
680 231169718
189 240587432
253 119812393
68 1000000000
39 108607630
196 11346291
975 13406438
957 27861351
556 134298268
352 39254941
847 18328074
573 258427390
39 72456167
667 6291678
573 115040612
843 336923315
585 149817729
724 50621356
962 21500100
471 105529081
952 134856020
659 458393369
429 224209233
817 160384613
382 16492518
465 107595083
710 269458458
226 1000000000
339 113848678
613 464518570
909 16949940
609 599915214
397 306157137
919 723809447
979 464537369
110 43354081
126 141210049
463 40169223
454 85659486
553 316604573
973 123977585
845 52819300
200 286604590
347 16109068
234 1000000000
706 164871325
121 525118290
203 77301633
925 49655481
925 303982141
327 47206873
809 134878151
767 447163578
54 1000000000
252 41810986
717 305811353
175 429523899
94 490543945
175 23181545
352 275797340
589 1000000000
516 1000000000
649 6812774
129 142504944
858 341879490
232 21646573
808 1000000000
296 154993703
828 1893659
114 179523799
182 36304235
493 402812144
557 77555805
770 2261313
930 15779478
289 466493018
940 431979239
153 9608184
924 445330822
651 120714231
82 15797827
822 245207408
29 75131633
91 542030441
270 1000000000
361 91354098
596 92636566
241 1000000000
680 1000000000
75 5316829
881 545119922
270 52534025
976 415591286
867 862552
92 368063920
993 138424543
262 89830088
953 32672755
630 314621299
130 294338435
827 1000000000
277 1000000000
814 85704977
546 1000000000
702 69343883
816 272026586
460 944746205
351 255091894
751 774935868
344 42753041
144 93251894
323 243571594
78 252566928
719 380781821
243 75928538
501 84840710
132 174925836
101 19231114
907 68425352
270 1000000000
216 17811378
536 181073410
970 689835679
972 85408589
794 57286292
770 540885974
992 269887728
409 276321827
307 248868916
330 17456881
395 148078906
524 258584447
609 459572173
504 485605952
125 507827851
86 400237806
78 381591718
549 234100193
205 371029521
533 196729556
178 133009555
991 88491203
188 56301550
651 243428379
771 159951903
72 309968368
40 264971345
687 84502754
579 93509131
80 1000000000
59 354469243
394 1000000000
73 1000000000
589 426588103
660 1000000000
458 22158609
141 75248487
841 33420588
259 1000000000
337 179078987
319 475537674
931 484268693
609 76763323
606 606481142
848 531363834
771 519173065
293 166791122
578 74565553
143 18772252
146 1000000000
263 163246015
243 161770943
412 32802732
903 24133583
335 262094503
251 169290710
736 45180028
666 53281876
286 284611817
433 55492729
193 1000000000
235 777395992
51 25192108
902 1000000000
49 333353393
90 212736893
70 230666698
480 59580747
432 1000000000
896 15632434
903 930029458
913 1000000000
908 482368259
196 433708972
751 503630831
8 1000000000
495 208483834
190 16042185
804 211787738
462 258885815
832 152057279
463 3364171
856 317499963
257 436687858
927 302296328
110 42060828
299 115427537
547 115668733
20 261488844
59 4012144
955 71541120
83 332170757
552 323252926
118 608691
506 130314551
842 970295495
306 782990862
599 337530483
647 12166445
183 1000000000
202 108147492
495 27959779
147 248686258
705 207146734
809 130931667
117 4705631
868 364239922
787 191024295
301 94567302
705 18396731
108 693577821
210 55177833
832 89566416
708 86685758
10 151274600
688 91711038
497 69026585
549 19940998
110 422213574
147 123992670
529 518224838
860 231993079
1 132040885
734 196678737
879 218339312
105 353970359
370 51482268
422 182075758
843 204945208
981 65976769
337 9806593
925 434417153
637 329387274
270 299946219
486 310683897
346 363567523
317 128738583
366 649339462
810 139060568
517 107837345
124 185441865
213 237146748
844 292540131
206 291342766
777 77367324
857 407602946
412 106442644
182 1000000000
780 118059816
428 474032791
130 288492819
932 19140306
190 117907117
989 162106903
439 269857230
224 1000000000
285 410783765
660 304971932
633 845281
578 20864797
211 305239599
938 26052949
666 134901155
11 1000000000
119 226644434
61 657083302
922 33837772
690 11967275
90 228559323
983 1000000000
991 177742275
39 66388078
891 109578642
72 951601933
155 142255771
922 70570401
793 15725004
846 1921292
517 1000000000
508 100352287
479 107350546
683 96967189
294 33113149
852 50950896
842 229299259
782 314227077
308 154902640
818 4880932
708 24716236
63 58879549
609 3127939
502 895863015
4 224049751
871 5712010
932 230090327
401 194259686
450 122173385
596 28262769
349 61240710
298 970893334
862 173076591
56 146124943
837 1000000000
905 205744615
625 11106915
547 180291844
795 126406556
798 142001899
330 118931618
891 333918564
191 113865344
74 449970796
185 458341339
434 376363942
601 241997213
604 650587774
391 346403803
799 130465768
922 460966387
508 56634129
682 109550021
962 40089790
553 939694036
770 547126250
212 5439020
772 48551615
78 25119331
167 1000000000
981 1000000000
540 1000000000
673 456109828
938 89105738
83 314319954
178 1000000000
51 307235251
859 140400856
704 1000000000
78 1000000000
114 14935920
626 30700798
139 30450086
232 167290068
656 240800764
808 268832663
372 11166190
921 282920170
445 134331979
196 514236210
403 327502208
96 208775378
791 136079940
566 93549560
49 242629174
181 42688887
664 400988154
838 848366128
413 57523960
25 90600815
999 1000000000
317 1000000000
39 282164768
371 317493714
733 251100448
698 226232924
600 538993454
707 726688214
288 3709750
765 707688042
6 573165928
161 143002099
866 148353868
70 144581386
691 2481323
925 8025623
514 1000000000
478 54170806
462 437685901
200 182958026
200 42885606
204 317726537
16 1000000000
321 44339869
205 149453126
528 515857312
216 230911346
793 42958560
288 69094539
410 60447949
774 351070692
478 140189749
505 9767791
771 377192449
26 209827018
34 327455942
800 429748459
306 260262613
212 1000000000
524 110863690
710 309081773
559 95444881
621 189678239
596 14697633
634 101456193
451 35161170
948 1000000000
347 159833820
252 188557487
404 80301928
105 410602514
31 72004080
4 271535818
580 76318002
621 189823420
506 167501066
907 97826252
426 160807902
494 1000000000
28 163537940
703 322202042
327 279679012
278 293505505
835 946752828
370 236759168
241 5315835
508 98583150
289 124381000
324 283632077
426 1000000000
865 30126717
93 381728254
307 159301321
601 232796046
932 674771551
415 140902519
945 82081837
111 150211721
244 88976996
360 69097473
125 78302593
682 107510254
764 34989574
838 31397908
424 1000000000
324 7868304
489 920526750
203 59321224
160 84684380
524 1000000000
933 755985094
247 355268393
775 273492586
819 349595932
199 136102870
840 92803595
292 4917903
687 30777182
655 423924435
808 109575562
159 411713030
194 7157151
877 94790673
310 114606336
273 1000000000
827 192179403
818 1000000000
426 82223292
497 388109131
163 1000000000
485 1000000000
429 449009107
95 98427326
792 153222188
614 387400851
198 154428322
51 5757734
844 20342508
838 1136871
453 1000000000
190 655244366
950 362608425
259 1000000000
58 163462439
903 1000000000
63 425240607
47 45624211
277 105071235
46 26042522
141 517068411
82 339821447
543 34494345
443 210511486
266 92564420
250 148115516
711 159353328
671 63965078
333 211143820
361 544819598
629 445134
256 619970328
63 333237722
934 20548448
890 274796625
344 54141958
342 995852326
169 86572106
621 13910589
823 1000000000
548 29118522
770 187057339
846 109775184
899 265663046
185 651315622
562 14745278
13 535359678
278 1000000000
563 255491924
184 182101873
354 510338609
367 1000000000
4 1000000000
316 526535566
590 367215631
103 253742060
762 5844161
335 29388757
632 1298367
732 235930884
600 1236551
159 109556550
344 293269355
712 64047487
227 1000000000
902 10237148
511 416610101
970 1000000000
869 328888156
963 92664211
508 1842263
738 1000000000
148 1000000000
679 384298520
167 401670920
585 157588418
211 546672573
457 174678509
304 49842229
414 4343338
263 386327814
873 122676784
688 130879067
513 594429822
842 235439256
791 19875643
717 236355002
410 674178452
339 532368436
827 85432735
921 1000000000
970 18430541
602 1000000000
206 535660305
412 147475505
288 22309934
783 162351900
911 96399668
148 61949525
772 1000000000
419 606067430
238 375769932
659 64824139
190 202163009
677 185183936
340 592836534
240 825425633
951 1000000000
613 123830640
935 485827291
259 298433158
157 237415383
171 104503434
977 667002161
117 275388655
626 1000000000
656 17167673
121 274538346
860 63493670
126 302952580
427 101471069
40 158475955
346 374170229
423 5329800
4 83195003
245 1000000000
423 1000000000
815 41231462
579 522616346
991 136334072
417 431943078
5 788466179
705 86132450
321 213387701
266 25842955
786 18481618
205 547823230
312 154026445
361 261261696
668 28075900
119 16204727
22 674722217
926 564731246
85 84933180
751 34849818
258 123509507
194 67713075
132 488027998
814 80754083
492 43641340
515 128092086
985 709730579
67 123281369
636 983793007
844 34191612
429 267747853
358 169964878
595 537939819
874 84290668
399 353306951
15 13290740
544 63304162
606 1000000000
463 182621
855 96599194
723 22231450
841 534729155
389 280065276
989 96278095
277 258331845
474 118244060
18 184244080
721 142909
988 636583855
361 86965526
901 428407491
139 357761840
338 1000000000
47 374056224
422 497653052
420 203497978
15 135560065
579 153400254
973 267798988
19 1000000000
545 59820523
157 18376143
683 307932142
416 482495330
202 284443185
133 108158112
294 58101018
435 51309434
177 219722964
651 715108982
712 121157584
653 29024770
278 22170825
976 1000000000
321 109658108
517 627583797
465 28915304
995 33493954
863 56029099
691 85766141
771 322078298
228 466082795
164 16325466
535 28127502
739 341115077
524 215688221
631 108253783
858 218327217
297 124273579
90 267853108
425 1000000000
819 1000000000
734 231166219
126 143013232
96 46445700
906 297938710
824 164142257
288 56608341
294 197897845
543 161448198
465 42041134
952 508686
18 131421194
379 280225963
216 705541747
551 42452599
556 69792721
37 22510304
134 40862396
516 113820110
869 6885570
941 7703032
978 101780452
200 82296561
924 293512898
668 103496832
260 132434205
633 123335531
385 137613705
80 1000000000
436 153878788
809 79475924
500 71927578
131 392831997
378 363445288
695 1000000000
518 20504407
612 221555886
855 139500647
891 60088424
198 115946464
236 140177990
18 337830364
518 145992571
220 195989927
73 115934765
899 8239852
406 383669409
936 1000000000
349 447493149
755 1000000000
29 29044374
651 1000000000
815 40174235
200 540494944
739 481018654
931 981650084
704 274724978
876 46740410
430 170161720
706 85226670
278 146699134
614 8098844
480 20046125
144 79893747
995 807222950
455 53563704
64 10428606
931 134570542
374 1000000000
198 117625398
918 465692911
101 197479436
456 300169279
706 41255234
235 30150220
181 111754311
543 235604091
222 183062012
661 821416224
980 825937049
29 170858355
311 818782296
574 1000000000
736 456307747
825 28123076
207 82389278
894 560306601
467 120833571
276 222746338
621 126688703
907 422072633
276 646447002
244 449506871
129 146664044
351 7832418
915 910487460
795 170958401
155 463005459
905 338240306
385 43985703
512 105366534
940 1000000000
521 143618622
789 1000000000
396 5897355
819 57539132
152 384832531
399 9842872
85 290249127
488 369512323
749 183590655
271 50679598
405 1000000000
4 158205503
592 103310753
174 69613882
835 289289691
605 450710446
665 221955211
171 367349131
128 385310874
973 827599445
64 422273092
582 7983506
234 20688458
76 107815204
878 707946906
383 1000000000
523 286080956
680 364506655
154 556732319
863 90994220
698 65215804
755 1816675
452 873481744
700 884787078
392 119258777
428 197287714
381 504606686
312 62377299
219 18278561
563 170548173
916 449057391
243 127590051
45 27071415
296 23863913
345 410864589
59 282961215
982 47810767
380 516077442
348 263207727
58 68700467
812 105395283
966 27613482
861 42650358
703 33658609
57 187577080
718 47810313
949 122617670
707 340311024
59 265631676
973 5926505
499 350150448
756 104409020
781 9039131
689 565733941
911 120326681
196 186543796
116 1000000000
508 214077866
146 72098635
378 1000000000
282 498812393
725 292459753
155 1000000000
686 471830504
389 238203388
205 15723676
290 164030027
1 172189512
968 149769143
691 321690126
943 28167963
738 12624576
72 535988558
719 90492231
795 9486822
289 715034043
431 49042499
673 108926259
900 1000000000
446 27929177
340 827353670
825 378748666
788 26047968
594 123913434
807 11045952
744 158991557
187 82779253
116 124475518
888 21539295
437 1000000000
63 386270572
964 19072179
368 73183049
368 151995230
618 299860568
418 36164008
814 148936663
786 18188911
707 92397658
687 75497502
578 1000000000
833 514776671
346 1000000000
441 580243601
868 27174069
271 16541133
472 137317407
203 108249373
341 271803190
371 358443703
787 476575823
786 115191214
172 262575014
518 29579153
765 553250816
799 56417821
121 175377913
663 80935658
38 388865609
587 200570705
916 1000000000
61 264521954
900 374427374
797 51531461
614 265217271
67 2525682
905 82379418
262 201003934
414 40912532
774 454187663
116 98260287
92 164463846
764 72211747
584 24574934
805 52947754
601 27502669
896 359171200
944 19067288
677 591121190
340 258229232
931 1000000000
454 354778534
451 242017967
421 423713084
596 407417606
898 18753150
559 143926258
437 278774965
619 400396059
197 1000000000
985 1000000000
939 636128411
160 1817724
334 273236714
73 71781600
895 27798340
628 191047736
837 749094
832 388210093
249 1000000000
974 44823721
755 182991379
789 426857029
274 18423615
510 46038650
294 333163776
736 45771488
473 44642623
836 212612692
464 392707204
906 206708860
910 284861365
601 247339499
673 13202952
866 81580832
489 19827202
60 1000000000
919 39708543
968 614291270
299 267483063
29 4424490
28 38392420
252 191337797
466 104842082
628 1000000000
359 1000000000
230 1000000000
905 138741974
962 30518428
776 415615370
87 62088754
613 713205428
502 245942947
631 339822603
406 102218404
199 1000000000
488 1000000000
221 3871081
771 209998482
968 34249009
320 120481966
649 42906801
335 15061201
327 326465781
575 384708413
803 47660943
689 221826477
245 505516508
892 29000403
356 253424578
785 84290830
968 56070512
351 431279130
546 187587863
871 13963568
930 119600545
296 62529042
999 19638094
580 354827772
130 1000000000
416 316734866
410 3666721
166 1000000000
32 132469799
958 8679625
644 432338402
447 201954646
805 54065247
650 59545938
500 52378006
855 438806446
976 24681614
341 1000000000
194 159259629
108 404815809
57 117802341
525 280455078
982 3433615
528 149087359
408 1000000000
948 232316536
152 10638249
930 220691075
990 44006772
33 106289969
489 176025771
434 20128952
426 313097846
685 2537565
904 710606133
385 17802300
652 243676060
70 472088794
477 6879471
141 125499558
516 794128282
974 127076201
625 340145531
944 479925240
763 24540551
436 4314842
386 139182443
266 23394944
495 85309958
265 283760092
530 44582463
89 10121673
179 747652661
587 607846166
528 73692998
879 156611054
156 136636853
940 54470866
621 203878298
379 120075197
907 267291920
379 31930965
96 13568116
957 212259905
601 252257390
985 243268961
320 350848520
478 86946326
533 37301291
748 145805272
536 162728335
940 142849614
336 279270595
726 290654209
853 49787798
585 52374355
872 240995168
358 464105417
289 91314430
445 111601175
943 75488622
629 373436508
763 24577921
710 26839031
628 74680943
561 97464478
235 7812367
542 228551827
879 349302088
860 37695024
209 641130419
220 72988373
769 430932194
197 164187983
214 161204251
536 643538364
105 351718529
189 183639014
297 10923731
539 32499203
167 1000000000
386 374073813
938 24261893
476 155939028
907 738135005
414 1000000000
562 118468067
931 253233349
254 1000000000
88 416130853
447 420476479
632 1000000000
239 91761350
329 469956253
987 19898483
339 478181482
734 41197961
711 300382740
878 291755187
749 14283747
779 30727259
916 19252004
174 654567104
909 115278868
191 150983872
199 229695603
869 117919656
107 393105072
352 1000000000
273 31671509
122 17974243
280 98122866
569 265055739
249 210200087
53 10473789
227 389957236
655 1485648
94 12108538
102 88904654
876 622904655
435 75157119
147 1000000000
406 41785871
483 3502970
262 112618062
805 162661593
44 118144723
512 411135171
295 1127938
70 25297068
864 519341024
644 12498034
71 200929686
196 103063764
59 110707682
774 64062145
852 152856057
994 106518091
699 132493755
590 472860182
192 190891175
213 79107588
498 1000000000
173 336166973
154 133916111
751 15941720
391 303919374
10 77671056
186 367184930
662 280796658
731 448314816
109 306957737
785 1000000000
909 1000000000
613 297586508
574 810662093
862 1000000000
953 36237892
485 200038228
166 828757692
385 56508838
404 360134789
27 224525736
243 91782108
26 108862959
413 62482722
583 1000000000
391 516584745
930 16611487
940 5388706
746 8592853
938 74343600
496 413114071
409 103310210
819 221592498
906 10809742
772 1000000000
701 552721149
90 705535447
633 184727621
678 775786810
271 137284812
968 459181371
182 339310798
111 3604720
7 70354497
651 236637301
473 1000000000
469 136960425
637 127312765
381 54672453
547 177203801
899 227649
698 247429113
621 30008082
482 310867717
14 134070268
949 697065076
524 34154313
136 379604298
623 123469548
126 707201639
849 82812373
325 406443994
775 1000000000
653 315482983
316 162001008
727 158346760
45 157191726
363 1000000000
813 239018825
744 359511029
146 219814081
807 9881724
860 112353424
919 55494866
980 121706141
9 720973542
850 382380566
140 228511609
669 1000000000
273 69478038
598 34069209
240 33348015
300 101884026
152 58646028
320 27226510
938 11255148
929 1000000000
933 1000000000
688 1000000000
434 341866103
901 281835053
536 65222885
759 103594980
768 4295543
759 528504723
801 14684711
556 1000000000
340 471852579
575 572836726
633 1000000000
775 77008209
87 360948599
797 13994803
415 72785334
969 254190248
64 22271362
914 394899194
435 403015252
848 331854248
799 445184557
917 42911810
69 73689426
606 117753802
941 99709516
942 48037103
782 75311263
811 456203811
665 49373344
661 566422003
861 426817216
661 385588626
171 345610644
35 202602066
666 114359780
910 31117589
971 8986707
710 32295288
829 412061182
461 117501854
201 1000000000
833 16336301
503 409584120
114 568474077
214 49143487
129 403855765
247 121081950
749 8639351
729 293892347
95 1000000000
373 298685928
631 193683436
138 201141493
668 326915645
633 111468237
223 216883014
218 129304491
815 1000000000
292 247380427
421 101845677
352 85477498
41 193884365
205 20977891
522 3471885
988 988982200
112 489272215
684 45063723
956 355361617
894 289600249
30 47098323
385 221977169
445 947779256
463 276434154
706 79444276
53 185707462
85 9692328
413 916044780
404 284179033
407 155861881
778 71756563
194 309345602
877 33403073
743 242574027
942 307098172
910 119857585
156 686170736
774 21040963
600 331775720
471 495503070
345 419034527
338 18654685
528 1000000000
607 28256512
404 6253070
389 9662930
222 1000000000
357 196871687
886 411415788
510 1000000000
675 27391425
297 124813558
958 5149919
854 38468222
566 337048332
972 190790428
964 345714852
203 257368722
959 1000000000
740 141268458
184 40996623
167 1000000000
7 1000000000
35 212413756
899 38490837
441 1000000000
588 14704868
857 365871004
579 1000000000
258 324616662
328 389323658
580 1000000000
579 1000000000
832 1000000000
266 13307829
966 1789082
448 136022150
549 118646080
51 1000000000
198 51872695
995 183389514
768 15261717
50 268940100
796 373434150
709 65456835
370 383473032
799 41187757
721 411624365
117 338144150
25 16937874
386 451357274
363 609770567
996 216166045
847 154538657
627 716761012
4 151738835
840 9606848
947 1000000000
907 44731519
780 63411944
851 497169299
638 29315742
545 772429773
673 23690492
860 654430755
966 59310883
333 587778962
309 301181316
867 1000000000
173 413743618
639 478921913
367 148392264
769 162991536
498 1000000000
584 81380462
103 113532182
501 37208436
134 437601526
647 203068781
782 212424500
551 382033
823 6345969
980 1000000000
547 1000000000
95 542252229
903 481837996
320 416391823
574 442982276
6 45731097
589 348936288
57 1000000000
695 79759913
611 433984866
426 20045655
297 185388843
446 253441462
566 89540125
748 294997808
448 30361998
500 498345246
839 416350203
973 593872248
716 110741782
576 192386692
775 295995467
836 527543486
231 2120907
978 34668183
556 73807538
106 123858400
344 294186095
667 92293724
393 922996464
646 629918862
791 634441
322 43384539
403 47906984
287 690960654
532 78450622
911 133335962
83 126157985
920 673992806
944 132923186
290 12748379
210 863739634
790 45128403
90 789390800
603 146790181
159 44970510
971 91865124
282 2450110
843 872330
411 1000000000
381 573625905
193 188578157
769 14182204
940 718810470
215 371201059
69 47431647
382 202565635
316 99917253
798 1000000000
112 23078927
856 252164531
10 208550892
204 64795506
514 32961885
225 333991426
430 739762391
600 240286097
193 7999189
128 50119901
609 71007028
466 115844491
95 359271491
253 1000000000
98 1000000000
690 12066775
387 6027804
121 158613508
897 199224198
593 75762180
485 87480653
794 136373919
894 1000000000
110 128019288
669 119487922
186 1000000000
426 264372067
401 8326911
516 755135212
129 280976070
756 593909497
210 117980772
937 91376036
293 149177135
508 590076153
922 122416865
748 14626185
160 124369426
562 39938587
144 546992630
430 27720214
393 83697786
191 147877580
340 1000000000
565 1000000000
312 65245635
705 402722096
934 219980756
115 617618448
646 119886080
3 2609798
471 52324837
231 44523816
481 66845090
738 263396793
582 26357307
458 161109085
747 215272518
719 189207930
979 14385411
627 32708840
588 1000000000
659 48281642
198 148071897
154 23717307
258 3349917
525 132747905
464 347733057
807 303002711
623 70992857
678 72101963
128 245758373
682 935671320
458 182430
620 1000000000
582 109709785
180 6339667
243 952843407
401 92897350
458 111899178
396 143571291
851 1000000000
724 189209887
661 126934605
858 29750347
961 1000000000
85 774808014
310 127964840
102 93106580
157 202997186
941 22824059
261 431927212
121 118786766
903 1000000000
171 67610762
954 1000000000
610 216854950
343 1000000000
647 823282203
462 104522458
809 281907073
318 247849570
873 269129784
736 208359393
695 108519825
259 174337904
2 167328363
400 3597005
418 121679721
646 334812382
17 680317711
566 295764778
412 1000000000
696 586047331
150 20730558
923 1000000000
733 114594591
176 59909876
593 4818389
270 214787713
763 366208240
782 267961990
75 8143866
239 176640767
424 635683428
938 174373052
410 77636744
870 112564877
371 692650218
4 1000000000
553 82643323
428 255766912
188 438364960
29 7527764
485 476319917
272 132713544
867 118520595
692 265162154
823 51786467
578 608890356
985 283813321
153 407998655
880 359440262
498 818439442
205 65942868
445 25172936
855 41869291
721 511815116
743 395931413
847 622674973
765 159255351
454 1000000000
200 69953536
887 108729403
392 1000000000
273 72667783
22 332153142
29 128287280
306 104405632
178 268440668
187 89504968
970 34139287
34 179635543
514 627162253
679 219302719
772 1000000000
424 20823341
368 187910900
880 77036360
485 100959773
389 153975995
532 297356345
496 1000000000
933 239440987
80 400400193
295 221222270
630 4059102
842 186881484
561 308010131
151 144990186
90 303012841
782 363455977
720 1000000000
150 163983392
452 1000000000
584 4501186
326 675766434
451 1000000000
405 40867657
736 244807321
42 107935089
207 409445271
508 504432772
431 347586557
924 1000000000
312 36472636
249 302106756
547 75779776
340 1000000000
64 31898095
781 29902488
942 463935331
499 633870869